作者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/cn.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