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