推 yp195126: 1.3 F 如果每個數都對應到同一格 這樣chain長度為n 最長 01/19 23:48
→ yp195126: 搜尋時間為O(n) 01/19 23:48
推 yp195126: 演算法1.2 如果是skew-tree 需要O(n) 可以畫圖實作看看 01/19 23:52
→ yp195126: 演算法1.3 merge A1A2A3成一個sort list需要O(n+n+n)=O( 01/20 00:22
→ yp195126: n) 因為是balance bst 所以root需為中間值 在list找到中 01/20 00:22
→ yp195126: 間值的時間為O(1) 用遞迴概念 T(n)=2T(n/2)+O(1)=O(n) 01/20 00:22
→ yp195126: 兩者相加為O(n) 01/20 00:22
→ dumpling1234: 想問ㄧ下第三題 如果list用AVL tree去maintain的話 01/20 00:38
→ dumpling1234: 不是可以達到O(logn)嗎? 01/20 00:39
→ yp195126: logn是單項操作的時間吧 要再乘上n 因為題目給的是low b 01/20 00:46
→ yp195126: ound 但有辦法在小於O(nlogn)的時間求出 01/20 00:46
→ yp195126: 所以答案是F 01/20 00:48
→ dumpling1234: 我說的是DS Hash 那題 01/20 01:09
推 yp195126: Chaining mouther是以link list的方式去串聯同一格的值 01/20 01:15
→ yp195126: 搜尋時間比照link list 01/20 01:15
→ yp195126: 是chaining method...選錯字 01/20 01:15
推 moriahyen: 想同問M是什麼?? 常數嗎?? 01/20 10:12
→ st474ddr: 感謝大大們 01/20 11:24
→ alen0303: 關於那個M 台大考過類似題 是當變數來看 01/20 14:18