[理工] 104台大 資料結構

看板Grad-ProbAsk作者 (O_O)時間7年前 (2017/01/15 12:19), 7年前編輯推噓4(4推 0噓 54→)
留言58則, 6人參與, 最新討論串1/1
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
→
01/15 12:36, , 1F
因為 single unsort or sort link 無法判別 先行者
01/15 12:36, 1F
→
01/15 12:36, , 2F
的位置 要重新search 找到其位子
01/15 12:36, 2F
→
01/15 12:39, , 3F
這是楓葉的考題
01/15 12:39, 3F
→
01/15 12:39, , 4F
搞定表格內的時間複雜度 你就會你問的那題了
01/15 12:39, 4F
嗯嗯我懂你的意思！但是為什麼在第一個小題中卻是O(1)呢 ※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 12:43:07
→
01/15 12:44, , 5F
上面那題 你已經畫起來關鍵字了 它是用singly link
01/15 12:44, 5F
→
01/15 12:44, , 6F
加 index 代表它有紀錄
01/15 12:44, 6F
→
01/15 12:47, , 7F
紀錄各link所代表的編號 故 O(1)
01/15 12:47, 7F
所以我的內心就一直很掙扎..若是有編號那為什麼第一個還要花O(n)去Access..Orz ※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 12:48:54
→
01/15 12:48, , 8F
比較麻煩的是insert 目前只能把它假設為unsort link
01/15 12:48, 8F
→
01/15 12:48, , 9F
list 若為sort 則為O(n)
01/15 12:48, 9F
若有sort感覺就會提起（像是這份考古的第5題） ※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 12:50:40
→
01/15 12:51, , 10F
你想像access為search index 可能比較好理解
01/15 12:51, 10F
→
01/15 12:53, , 11F
Access不會一個一個確認 是否為該資料 而是確定某資
01/15 12:53, 11F
→
01/15 12:53, , 12F
料在某個index中 只要memory 去尋找該index編號即可
01/15 12:53, 12F
→
01/15 12:53, , 13F
找到
01/15 12:53, 13F
可以這樣理解嗎： 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
→
01/15 13:00, , 14F
另外提一下 假如double link 的remote定義是 尋找該
01/15 13:00, 14F
→
01/15 13:00, , 15F
點並刪除則為O(n)
01/15 13:00, 15F
→
01/15 13:03, , 16F
純remote ，single link 為search +remote 若為我上
01/15 13:03, 16F
→
01/15 13:03, , 17F
面提到的定義則可為兩search + remote or search+rem
01/15 13:03, 17F
→
01/15 13:03, , 18F
ote
01/15 13:03, 18F
→
01/15 13:04, , 19F
你兩個理解都跟我的理解一樣
01/15 13:04, 19F
→
01/15 13:08, , 20F
Single sort link為O(log n) binary search 我上面
01/15 13:08, 20F
→
01/15 13:08, , 21F
打錯了
01/15 13:08, 21F
不太懂k大的補充，所以delete跟remove不同嗎@@ 是指說純delete是O(1)而純remove要先search所以是O(n)？ ※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 13:16:43
→
01/15 13:20, , 22F
應該說 沒有index 的singly link list 需要 search +
01/15 13:20, 22F
→
01/15 13:20, , 23F
remote
01/15 13:20, 23F
→
01/15 13:21, , 24F
若題目純論delete link list 就只是delete 該pointer
01/15 13:21, 24F
→
01/15 13:21, , 25F
沒錯
01/15 13:21, 25F
懂了！感謝k大耐心解釋m(_ _)m ※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 13:22:23
→
01/15 13:22, , 26F
主要差別是依題目有沒有singly link 這個關鍵字為主
01/15 13:22, 26F
差別在於..? 不然題型會有什麼其他的link list型呢（只寫過交、台考古QQ） ※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 13:23:46
→
01/15 13:23, , 27F
看他需不需要討論到這麼深入
01/15 13:23, 27F
→
01/15 13:35, , 28F
我經驗是類似這種多段敘述 且有提到single link 就要
01/15 13:35, 28F
→
01/15 13:35, , 29F
小心啦@@
01/15 13:35, 29F
→
01/15 13:37, , 30F
純談論link list 就不分double link or singly link
01/15 13:37, 30F
→
01/15 13:37, , 31F
即可最低到O(1) （大概吧？
01/15 13:37, 31F
應該是的XD 感恩! ※ 編輯: ssssIssss (140.112.25.105), 01/15/2017 13:45:52
→
01/15 14:15, , 32F
用C++的vector來看, Insert跟Delete都是直接對Index作存
01/15 14:15, 32F
→
01/15 14:17, , 33F
取操作資料, 所以複雜度=O(1)
01/15 14:17, 33F
→
01/15 14:19, , 34F
阿不對 他問用誰實作時存取的複雜度, 不要理我XD
01/15 14:19, 34F
推
01/15 14:40, , 35F
我還是有點不懂，為什麼singly linked list的Remove要
01/15 14:40, 35F
→
01/15 14:40, , 36F
O(n),而Doubly linked list只要O(1)呢
01/15 14:40, 36F
推
01/15 14:42, , 37F
還有楓葉的singly linked list和doubly linked list的
01/15 14:42, 37F
→
01/15 14:43, , 38F
Search(L,k)為什麼是花O(log(n)),我不是sequential sear
01/15 14:43, 38F
→
01/15 14:43, , 39F
ch下去，假設worst case花O(n)嗎？
01/15 14:43, 39F
我的理解是，在第二小部分中的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
→
01/15 21:15, , 40F
要已 sort 過才行 O(log n) 未sort 過順序是亂的
01/15 21:15, 40F
→
01/15 21:15, , 41F
已經排序過的當然可以先從中間值去檢視是大還是小
01/15 21:15, 41F
→
01/15 22:24, , 42F
但是有辦法O(1)就提取到中間的node嗎？
01/15 22:24, 42F
→
01/16 08:36, , 43F
我記得用argument data AVL可以做到lg n
01/16 08:36, 43F
→
01/16 10:38, , 44F
問一下 這題答案是正確的嗎？我在別的地方有看到不同答
01/16 10:38, 44F
→
01/16 10:38, , 45F
案@@
01/16 10:38, 45F
→
01/16 10:40, , 46F
然後我也覺得那張表格的logn怪怪的 單純的linked list沒
01/16 10:40, 46F
→
01/16 10:40, , 47F
辦法二分搜吧...
01/16 10:40, 47F
→
01/16 10:40, , 48F
01/16 10:40, 48F
→
01/16 10:42, , 49F
01/16 10:42, 49F
→
01/16 10:55, , 50F
傻眼 XDD 我被這張圖背叛了 我自己看的演算法答案也
01/16 10:55, 50F
→
01/16 10:55, , 51F
是寫 linear
01/16 10:55, 51F
→
01/16 10:57, , 52F
i.imgur.com/a/DuZxc 抱歉 是我錯了
01/16 10:57, 52F
→
01/16 10:57, , 53F
01/16 10:57, 53F
→
01/16 11:06, , 54F
等我今天複習完 argument data 在看可不可以好了@@
01/16 11:06, 54F
推
01/16 19:36, , 55F
是啊難怪看起來怪怪的,應該只有sorted arrary可以Binary
01/16 19:36, 55F
→
01/16 19:36, , 56F
search
01/16 19:36, 56F
→
01/17 20:06, , 57F
是的
01/17 20:06, 57F
推
01/24 14:42, , 58F
skip list 可以binary search唷
01/24 14:42, 58F
‣ 更多 ssssIssss 的文章
文章代碼(AID): #1OUlXYKJ (Grad-ProbAsk)