[理工] 104台大 資料結構

[ssssIssss (O_O)]

http://i.imgur.com/BW0mOK4.jpg

如圖，想請教第一題

為何在Vector時，link list的insert跟delete都是O(1)

但在下方list L時，singly link list的Remove卻要O(n)呢？

兩者間差異何在、還有，第一題link list在做Insert跟Delete時為什麼不需要先sort？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.165.121
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484453986.A.513.html
→ ken52011219: 因為 single unsort or sort link 無法判別 先行者
→ ken52011219: 的位置 要重新search 找到其位子
→ ken52011219:  http://i.imgur.com/lt4RfYz.jpg  這是楓葉的考題
→ ken52011219:  搞定表格內的時間複雜度 你就會你問的那題了
嗯嗯我懂你的意思！但是為什麼在第一個小題中卻是O(1)呢
※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 12:43:07
→ ken52011219: 上面那題 你已經畫起來關鍵字了  它是用singly link
→ ken52011219:  加 index 代表它有紀錄
→ ken52011219: 紀錄各link所代表的編號 故 O(1)
所以我的內心就一直很掙扎..若是有編號那為什麼第一個還要花O(n)去Access..Orz
※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 12:48:54
→ ken52011219: 比較麻煩的是insert 目前只能把它假設為unsort link
→ ken52011219:  list 若為sort 則為O(n)
若有sort感覺就會提起（像是這份考古的第5題）
※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 12:50:40
→ ken52011219: 你想像access為search index 可能比較好理解
→ ken52011219: Access不會一個一個確認 是否為該資料 而是確定某資
→ ken52011219: 料在某個index中 只要memory 去尋找該index編號即可
→ ken52011219: 找到
可以這樣理解嗎：

Access就是link一個一個index下去search到所需的index，所以要花O(n)

而Insert跟Delete只需著重在動作本身，而Vector有提供Index，所以不需要再花O(n)去
尋找前一個node
※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 13:01:06
→ ken52011219: 另外提一下 假如double link 的remote定義是 尋找該
→ ken52011219: 點並刪除則為O(n)
→ ken52011219: 純remote ，single link 為search +remote 若為我上
→ ken52011219: 面提到的定義則可為兩search + remote or search+rem
→ ken52011219: ote
→ ken52011219: 你兩個理解都跟我的理解一樣
→ ken52011219: Single sort link為O(log n) binary search 我上面
→ ken52011219: 打錯了
不太懂k大的補充，所以delete跟remove不同嗎@@

是指說純delete是O(1)而純remove要先search所以是O(n)？
※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 13:16:43
→ ken52011219: 應該說 沒有index 的singly link list 需要 search +
→ ken52011219:  remote
→ ken52011219: 若題目純論delete link list 就只是delete 該pointer
→ ken52011219: 沒錯
懂了！感謝k大耐心解釋m(_ _)m
※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 13:22:23
→ ken52011219: 主要差別是依題目有沒有singly link 這個關鍵字為主
差別在於..? 不然題型會有什麼其他的link list型呢（只寫過交、台考古QQ）
※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 13:23:46
→ ken52011219: 看他需不需要討論到這麼深入
→ ken52011219: 我經驗是類似這種多段敘述 且有提到single link 就要
→ ken52011219: 小心啦@@
→ ken52011219: 純談論link list 就不分double link or singly link
→ ken52011219: 即可最低到O(1) （大概吧？
應該是的XD 感恩!
※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 13:45:52
→ HEroKuma: 用C++的vector來看, Insert跟Delete都是直接對Index作存
→ HEroKuma: 取操作資料, 所以複雜度=O(1)
→ HEroKuma: 阿不對 他問用誰實作時存取的複雜度, 不要理我XD
推 Transfat: 我還是有點不懂，為什麼singly linked list的Remove要
→ Transfat: O(n),而Doubly linked list只要O(1)呢
推 Transfat: 還有楓葉的singly linked list和doubly linked list的
→ Transfat: Search(L,k)為什麼是花O(log(n)),我不是sequential sear
→ Transfat: ch下去，假設worst case花O(n)嗎？
我的理解是，在第二小部分中的link list，因為沒有index，所以singly linked list需
要花費O(n)找出前一個node（因為進行刪除時前一個node的link要指向刪除之點的下一個
node）

而Double linked list因為可以直接藉由左邊的link指向上個node，所以不用搜尋上一個
nose

而O(log(n))我就不懂了，因為binary search只支援Random Access才對...?
※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 15:16:23
→ ken52011219: 要已 sort 過才行 O(log n) 未sort 過順序是亂的
→ ken52011219: 已經排序過的當然可以先從中間值去檢視是大還是小
→ ssssIssss: 但是有辦法O(1)就提取到中間的node嗎？
→ ken52011219: 我記得用argument data AVL可以做到lg n
→ w181496: 問一下 這題答案是正確的嗎？我在別的地方有看到不同答
→ w181496: 案@@
→ w181496: 然後我也覺得那張表格的logn怪怪的 單純的linked list沒
→ w181496: 辦法二分搜吧...
→ w181496:  http://i.imgur.com/FTz70dY.jpg
→ w181496:  http://i.imgur.com/KLo2fUg.jpg
→ ken52011219: 傻眼 XDD 我被這張圖背叛了 我自己看的演算法答案也
→ ken52011219: 是寫 linear
→ ken52011219: i.imgur.com/a/DuZxc 抱歉 是我錯了
→ ken52011219: http://imgur.com/a/DuZxc
→ ken52011219: 等我今天複習完 argument data 在看可不可以好了@@
推 Transfat: 是啊難怪看起來怪怪的,應該只有sorted arrary可以Binary
→ Transfat: search
→ ssssIssss: 是的
推 aa06697: skip list 可以binary search唷