[理工] 103 成大 資演

看板Grad-ProbAsk作者 (howard)時間6年前 (2018/01/10 22:06), 編輯推噓6(6推 0噓 12→)
留言18則, 8人參與, 最新討論串1/1
題目如下： 演算法的第二題 https://imgur.com/j4NQUrN
資結的第三題 https://imgur.com/PkD5ngF
這兩題我沒有答案 想問問看板上各位的想法 演算法的那題我寫 Ｔ 資結那題我寫 Ｆ 期末考大家加油喔！！！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.80.130.226 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1515593160.A.781.html
推
01/10 23:05, 6年前 , 1F
資結F+1
01/10 23:05, 1F
推
01/10 23:13, 6年前 , 2F
資結錯在哪，如果用rbtree來chain
01/10 23:13, 2F
推
01/10 23:14, 6年前 , 3F
資結F，只用chaining的worst case是東西塞同一格，O(n)
01/10 23:14, 3F
→
01/10 23:15, 6年前 , 4F
除非像w大說的用rbtree或avltree連結才能O(logn)
01/10 23:15, 4F
→
01/10 23:17, 6年前 , 5F
再看一下發現題目是寫could，那好像該選T @@
01/10 23:17, 5F
→
01/10 23:27, 6年前 , 6F
不過我覺得是0(1)
01/10 23:27, 6F
推
01/10 23:51, 6年前 , 7F
Chaining這種方式應該就是單純的串在後面吧！我也覺得是
01/10 23:51, 7F
→
01/10 23:51, 6年前 , 8F
O(n)
01/10 23:51, 8F
→
01/11 08:52, 6年前 , 9F
第一題應該是o(n) 反例是avl的skew tree
01/11 08:52, 9F
→
01/11 09:00, 6年前 , 10F
第二題我覺得仍然是O(n) 題意應該是要用worst case去看
01/11 09:00, 10F
→
01/11 11:56, 6年前 , 11F
avl 沒有skew tree
01/11 11:56, 11F
→
01/11 11:56, 6年前 , 12F
他是最平衡的樹唷
01/11 11:56, 12F
推
01/11 13:29, 6年前 , 13F
第一題是 O(n) 這是考 rotation distance 的概念
01/11 13:29, 13F
→
01/11 13:29, 6年前 , 14F
第二題 如果元素是有 order 的 那把 hash 到同一個位置的
01/11 13:29, 14F
→
01/11 13:31, 6年前 , 15F
的用紅黑樹存是可以把 worst case reduce 成 O(lg n)
01/11 13:31, 15F
→
01/11 13:31, 6年前 , 16F
但是不知道這種方法是不是仍然叫做 "chaining method"
01/11 13:31, 16F
推
01/11 13:33, 6年前 , 17F
01/11 13:33, 17F
→
01/12 22:33, , 18F
chaining method應該是特別指用linked list
01/12 22:33, 18F
‣ 更多 howard31622 的文章
文章代碼(AID): #1QLXt8U1 (Grad-ProbAsk)