作者jerry900287 ()
看板Grad-ProbAsk
標題[理工] 105/106 台大電機丙 資結
時間Sat Dec 23 23:18:40 2017
請教一下各位大大對於這兩題的看法
105 台大電機丙 資結 如圖
https://i.imgur.com/5tazIR9.png
這題 有多一個 equal 害我不知道應該是false 還是 true
因為他們 insert 都是 O( n log n )
這題不知道該用實際時間還是用複雜度時間...
還是這題的shorter是指樹的高度...?
106 台大電機丙 資結 如圖
https://i.imgur.com/1bYNigY.png
這個題目的意思
是有可能建完變成 balanced binary tree 嗎?
還是不管怎麼建都是 unbalanced binary tree ?
麻煩各位大大惹
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.243.91.60
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1514042324.A.20A.html
※ 編輯: jerry900287 (111.243.91.60), 12/23/2017 23:19:15
※ 編輯: jerry900287 (111.243.91.60), 12/23/2017 23:20:11
1F：→ winiel559: 覺得第一題是指樹高,false(三個點的時候)12/23 23:47
2F：推 FRAXIS: 這些是多選題嗎？12/24 06:17
上面是 是非
下面是 多選
※ 編輯: jerry900287 (61.230.131.29), 12/24/2017 09:42:53
3F：推 FRAXIS: 12 abc 都不對 d 是對的 12/24 11:11
4F：→ FRAXIS: e 的話是 O(n) 那題目寫 O(n log n) 應該也沒錯？ 12/24 11:12
5F：推 sarsman: 12.A的機率要怎麼算啊@@ 12/24 11:47
6F：推 FRAXIS: 你只要考慮 n = 2^k - 1 的情況 隨機插入變成 perfect 12/24 11:54
7F：→ FRAXIS: balanced search tree 機率非常非常小.. 12/24 11:54
8F：→ kidplayhappy: 12 (b) amortized的情況下為什麼不是O(log n) ? 12/24 12:10
9F：推 FRAXIS: expected 是 O(log n), amortized 應該不會是O(log n) 12/24 12:28
10F：→ FRAXIS: 因為 amortized 是指一連串的 operation 的 worst case 12/24 12:29
11F：→ FRAXIS: 執行時間 隨機插入的話 有 > 0 的機率 樹會非常不平衡 12/24 12:30
12F：→ FRAXIS: 所以 amortized 沒辦法是 O(log n) 12/24 12:30
13F：推 s06i06: 第一題我寫true,找不到反例，有大大可以找出個反例嗎 感 12/24 15:29
14F：→ s06i06: 謝 12/24 15:29
15F：→ kidplayhappy: 如果題目指的是樹高，這應該是反例 12/24 16:24
16F：→ kidplayhappy: 如果是執行時間AVL Tree應該會快一些 12/24 16:24
OK 那第一題應該沒問題了 謝謝你
18F：推 b10007034: e 為什麼比較緊的upper bound是O(n)？ 12/24 17:54
19F：→ b10007034: 不是直接建一個AVL tree 12/24 17:54
20F：→ b10007034: 給n個data，所以是O（nlogn）嗎？ 12/24 17:54
21F：→ b10007034: 順便問題目的意思，使不平衡變平衡，有這種演算法調整 12/24 17:56
22F：→ b10007034: 嗎？類似heap的bottom-up法 12/24 17:56
23F：推 FRAXIS: 先 inorder traverse 把元素存成 sorted array 12/24 20:30
24F：→ FRAXIS: 然後 sorted array 轉 balanced tree 12/24 20:30
25F：→ FRAXIS: 這樣作會使用額外 O(n) 的空間 不過實際上有其他方法可以 12/24 20:30
26F：→ FRAXIS: O(n) 時間 O(1) 空間把 unbalnaced tree變成balanced tree 12/24 20:31
27F：推 FRAXIS: 可以搜 Day–Stout–Warren algorithm 12/24 20:34
太神 那這樣 這題也沒問題了 感謝
28F：推 sarsman: 推F大，受益良多XD 12/24 21:36
29F：推 b10007034: 原來如此，又是一個thread bt應用嗎 12/25 09:33
30F：→ b10007034: 謝f大，順便問有些題目出題者的想法，我記得有時候題 12/25 09:35
31F：→ b10007034: 目的upper bound不夠緊，答案就會算錯 12/25 09:36
32F：→ b10007034: 那像這種時候，這題的e到底可不可以算對呢？還是要寫 12/25 09:37
33F：→ b10007034: 老師想看的答案？ 12/25 09:37
34F：推 FRAXIS: 我想除了改考卷的人之外沒人可以回答這問題吧.. 12/25 10:31
35F：推 winiel559: 我認為選擇題就選對的，計算、簡答題才要寫tight的 12/25 11:12
36F：→ winiel559: 我認為選擇題就選對的，計算、簡答題才要寫tight的 12/25 11:12
※ 編輯: jerry900287 (60.245.65.177), 12/25/2017 14:19:07
※ 編輯: jerry900287 (60.245.65.177), 12/25/2017 14:38:04
感謝各位陪小弟練劍QQ
※ 編輯: jerry900287 (60.245.65.177), 12/25/2017 14:38:41