[理工] 98台大資工link時間複雜度DS

[jas1123kimo (傑森)]

http://ppt.cc/jY8n

如題A為O(1)  B為O(lgn)  C為O(n)


2.4)各是B還是C?

9.10)各是A還是C?

感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
→ rnf0:連結有誤
不好意思，更新了，感恩
※ 編輯: jas1123kimo     來自: 123.241.44.21        (01/26 11:53)
→ rnf0:皆為C
→ jas1123kimo:Delete不是都是O(1)嗎，怎會變成O(N)sk
→ jas1123kimo:               呢?
→ rnf0:delete要把前一項的next指給下一項
→ rnf0:所以必須要search next==P的node,這要O(n)
→ rnf0:O(1)是free node而已,還要maintain前後的關係
→ jas1123kimo:所以11.12也是C嗎@_@?
→ rnf0:A
→ rnf0:可以直接拿到previous幹嘛search呢?
→ jas1123kimo:see 感恩!長知識
推 Bearcome:所以前幾篇有題DLL delete應該就是O(1)沒錯了
→ jas1123kimo:熊來你說9,10是A!?
推 Bearcome:不是 我是說台大電機101的某題
推 s07021990:101的delete跟這9.10的狀況不一樣吧
推 doubt2008:4是O(n),10是O(1),詳細可參考rnbjacky的詳解
→ doubt2008:此題的delete已經把要刪除的node用pointer指著了
→ doubt2008:完整題目：http://ppt.cc/4T9v
推 Bearcome:對SINGLE來說就算用P指著了 還是不知道上一個是誰不是嗎?
推 dennis2030:這題我認為Bearcom大說的是對的，不知道上一個node是誰
→ dennis2030:所以依然要花O(n)的時間去上個node，才能修正他的next
推 dennis2030:所以我認為10是O(n)
推 doubt2008:把P指著的node的下一個node的data搬到P指著的node
→ doubt2008:P指著的node的next指向 原本P指著的node的下一個node的
→ doubt2008:next
→ doubt2008:簡單來說就是知道欲刪除的node(A)和它的下一個node(B)
→ doubt2008:把B複製到A,再把B刪除,這樣不用知道A的前一個node
推 fine246:http://ppt.cc/1Vl~ 附上簡易的程式碼。缺點就是當刪除最
→ fine246:後一個點時，不能這樣做XD
→ rnf0:cool! 最後一個點直接free掉就好了
推 dennis2030:這樣會把pointer內的data改掉，會造成其他指令出錯吧?
推 doubt2008:最後一個直接free掉它的上一個指過去感覺會記憶體錯誤
→ doubt2008:所以還是要搜尋到最後一個的前一個,不過此題最後面有用
→ doubt2008:tail指著 所以還是不用搜尋
→ rnf0:直接free掉變null怎麼會錯呢? 最後一個會指向null
→ rnf0:C/C++不能這樣做的樣子orz,tail好像也沒辦法maintain
→ rnf0:因為tail的問題,worst case是O(n)
推 doubt2008:tail好像真的要前一個node才能,那就是O(n)了
→ doubt2008:另外回dennis大,若是有外部參考到B的話,會不知道B已經
→ doubt2008:變成他的下一個node了
→ doubt2008:說錯= = 上面說的B是A
→ rnf0:但如果用一個preTail來存tail's previous就可以O(1)
→ doubt2008:可是這樣變成要maintain preTail...因為刪除後preTail
→ doubt2008:要往前面一個node指
→ rnf0:只好再加一個prePreTail了.. (誤
→ rnf0:每次insert都存一塊錢,在delete tail花掉,amortized是O(1)