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

看板Grad-ProbAsk作者 (傑森)時間11年前 (2013/01/26 11:25), 編輯推噓12(12推 0噓 34→)
留言46則, 7人參與, 最新討論串1/1
http://ppt.cc/jY8n 如題A為O(1) B為O(lgn) C為O(n) 2.4)各是B還是C? 9.10)各是A還是C? 感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc)
→
01/26 11:49, , 1F
連結有誤
01/26 11:49, 1F
不好意思，更新了，感恩 ※ 編輯: jas1123kimo 來自: 123.241.44.21 (01/26 11:53)
→
01/26 11:58, , 2F
皆為C
01/26 11:58, 2F
→
01/26 12:12, , 3F
Delete不是都是O(1)嗎，怎會變成O(N)sk
01/26 12:12, 3F
→
01/26 12:12, , 4F
呢?
01/26 12:12, 4F
→
01/26 12:15, , 5F
delete要把前一項的next指給下一項
01/26 12:15, 5F
→
01/26 12:16, , 6F
所以必須要search next==P的node,這要O(n)
01/26 12:16, 6F
→
01/26 12:17, , 7F
O(1)是free node而已,還要maintain前後的關係
01/26 12:17, 7F
→
01/26 12:22, , 8F
所以11.12也是C嗎@_@?
01/26 12:22, 8F
→
01/26 12:27, , 9F
A
01/26 12:27, 9F
→
01/26 12:27, , 10F
可以直接拿到previous幹嘛search呢?
01/26 12:27, 10F
→
01/26 12:29, , 11F
see 感恩!長知識
01/26 12:29, 11F
推
01/26 12:32, , 12F
所以前幾篇有題DLL delete應該就是O(1)沒錯了
01/26 12:32, 12F
→
01/26 12:34, , 13F
熊來你說9,10是A!?
01/26 12:34, 13F
推
01/26 12:35, , 14F
不是 我是說台大電機101的某題
01/26 12:35, 14F
推
01/26 13:03, , 15F
101的delete跟這9.10的狀況不一樣吧
01/26 13:03, 15F
推
01/26 13:16, , 16F
4是O(n),10是O(1),詳細可參考rnbjacky的詳解
01/26 13:16, 16F
→
01/26 13:17, , 17F
此題的delete已經把要刪除的node用pointer指著了
01/26 13:17, 17F
→
01/26 13:22, , 18F
完整題目：http://ppt.cc/4T9v
01/26 13:22, 18F
推
01/26 13:28, , 19F
對SINGLE來說就算用P指著了 還是不知道上一個是誰不是嗎?
01/26 13:28, 19F
推
01/26 17:53, , 20F
這題我認為Bearcom大說的是對的，不知道上一個node是誰
01/26 17:53, 20F
→
01/26 17:53, , 21F
所以依然要花O(n)的時間去上個node，才能修正他的next
01/26 17:53, 21F
推
01/26 17:55, , 22F
所以我認為10是O(n)
01/26 17:55, 22F
推
01/26 19:42, , 23F
把P指著的node的下一個node的data搬到P指著的node
01/26 19:42, 23F
→
01/26 19:42, , 24F
P指著的node的next指向 原本P指著的node的下一個node的
01/26 19:42, 24F
→
01/26 19:43, , 25F
next
01/26 19:43, 25F
→
01/26 19:57, , 26F
簡單來說就是知道欲刪除的node(A)和它的下一個node(B)
01/26 19:57, 26F
→
01/26 19:58, , 27F
把B複製到A,再把B刪除,這樣不用知道A的前一個node
01/26 19:58, 27F
推
01/27 14:31, , 28F
http://ppt.cc/1Vl~ 附上簡易的程式碼。缺點就是當刪除最
01/27 14:31, 28F
→
01/27 14:31, , 29F
後一個點時，不能這樣做XD
01/27 14:31, 29F
→
01/27 15:42, , 30F
cool! 最後一個點直接free掉就好了
01/27 15:42, 30F
推
01/27 17:08, , 31F
這樣會把pointer內的data改掉，會造成其他指令出錯吧?
01/27 17:08, 31F
推
01/27 18:43, , 32F
最後一個直接free掉它的上一個指過去感覺會記憶體錯誤
01/27 18:43, 32F
→
01/27 18:44, , 33F
所以還是要搜尋到最後一個的前一個,不過此題最後面有用
01/27 18:44, 33F
→
01/27 18:44, , 34F
tail指著 所以還是不用搜尋
01/27 18:44, 34F
→
01/27 21:11, , 35F
直接free掉變null怎麼會錯呢? 最後一個會指向null
01/27 21:11, 35F
→
01/27 21:14, , 36F
C/C++不能這樣做的樣子orz,tail好像也沒辦法maintain
01/27 21:14, 36F
→
01/27 21:22, , 37F
因為tail的問題,worst case是O(n)
01/27 21:22, 37F
推
01/27 23:48, , 38F
tail好像真的要前一個node才能,那就是O(n)了
01/27 23:48, 38F
→
01/27 23:50, , 39F
另外回dennis大,若是有外部參考到B的話,會不知道B已經
01/27 23:50, 39F
→
01/27 23:51, , 40F
變成他的下一個node了
01/27 23:51, 40F
→
01/27 23:52, , 41F
說錯= = 上面說的B是A
01/27 23:52, 41F
→
01/28 08:06, , 42F
但如果用一個preTail來存tail's previous就可以O(1)
01/28 08:06, 42F
→
01/28 17:40, , 43F
可是這樣變成要maintain preTail...因為刪除後preTail
01/28 17:40, 43F
→
01/28 17:40, , 44F
要往前面一個node指
01/28 17:40, 44F
→
01/28 19:42, , 45F
只好再加一個prePreTail了.. (誤
01/28 19:42, 45F
→
01/28 21:14, , 46F
每次insert都存一塊錢,在delete tail花掉,amortized是O(1)
01/28 21:14, 46F
‣ 更多 jas1123kimo 的文章
文章代碼(AID): #1H0qoQDQ (Grad-ProbAsk)