[理工] 103 成大 資演

[howard31622 (howard)]

題目如下：
演算法的第二題
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
推 kssdpp222: 資結F+1
推 winiel559: 資結錯在哪，如果用rbtree來chain
推 sarsman: 資結F，只用chaining的worst case是東西塞同一格，O(n)
→ sarsman: 除非像w大說的用rbtree或avltree連結才能O(logn)
→ sarsman: 再看一下發現題目是寫could，那好像該選T @@
→ howard31622: 不過我覺得是0(1)
推 a1596482: Chaining這種方式應該就是單純的串在後面吧！我也覺得是
→ a1596482: O(n)
→ wsp50317: 第一題應該是o(n) 反例是avl的skew tree
→ wsp50317: 第二題我覺得仍然是O(n) 題意應該是要用worst case去看
→ howard31622: avl 沒有skew tree
→ howard31622: 他是最平衡的樹唷
推 FRAXIS: 第一題是 O(n) 這是考 rotation distance 的概念
→ FRAXIS: 第二題 如果元素是有 order 的 那把 hash 到同一個位置的
→ FRAXIS: 的用紅黑樹存是可以把 worst case reduce 成 O(lg n)
→ FRAXIS: 但是不知道這種方法是不是仍然叫做 "chaining method"
推 FRAXIS: https://goo.gl/84cjpi
→ DLHZ: chaining method應該是特別指用linked list