Question:
關於作業一的第一題,我不是很了解題目要我們寫些什麼。 請問是不是要算append跟reverse的big O? 還是說按照最後一行的hint,只要用append來implement reverse就好了?
Answer:
題目的意思是請同學先寫出 append 的程式碼。你的程式碼中 append (u, v) 所花費的時間 最多只要 m+n 個步驟(也就是 O(m+n) 的意思),其中 m 是串列 u 的長度, n 是串列 v 的長度。不過這裡我的題目出得略有失誤,其實 append (u, v) 所花費的時間 最多只要 m 個步驟 (O(m))就夠了,但這無損題目的原意。 然後,再用同學以上所寫的 append 程式,來製作 reverse 。其中 reverse (u) 所花費的時間 最多只要 m 個步驟(也就是 O(m) 的意思),其中 m 是串列 u 的長度。 (2009-03-18 加註:直接用 append 來製作 reverse 的話,所需時間會是 O(m^2) ,請留意。)