[理工] 105/106 台大電機丙 資結

[jerry900287 ()]

請教一下各位大大對於這兩題的看法


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://www.ptt.cc/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
→ winiel559: 覺得第一題是指樹高,false(三個點的時候)
推 FRAXIS: 這些是多選題嗎？
上面是 是非
下面是 多選
※ 編輯: jerry900287 (61.230.131.29), 12/24/2017 09:42:53
推 FRAXIS: 12 abc 都不對 d 是對的
→ FRAXIS: e 的話是 O(n) 那題目寫 O(n log n) 應該也沒錯？
推 sarsman: 12.A的機率要怎麼算啊@@
推 FRAXIS: 你只要考慮 n = 2^k - 1 的情況 隨機插入變成 perfect
→ FRAXIS: balanced search tree 機率非常非常小..
→ kidplayhappy: 12 (b) amortized的情況下為什麼不是O(log n) ?
推 FRAXIS: expected 是 O(log n), amortized 應該不會是O(log n)
→ FRAXIS: 因為 amortized 是指一連串的 operation 的 worst case
→ FRAXIS: 執行時間 隨機插入的話 有 > 0 的機率 樹會非常不平衡
→ FRAXIS: 所以 amortized 沒辦法是 O(log n)
推 s06i06: 第一題我寫true,找不到反例，有大大可以找出個反例嗎 感
→ s06i06: 謝
→ kidplayhappy: 如果題目指的是樹高，這應該是反例
→ kidplayhappy: 如果是執行時間AVL Tree應該會快一些
→ kidplayhappy: https://i.imgur.com/nN5HpGc.jpg
OK 那第一題應該沒問題了 謝謝你
推 b10007034: e 為什麼比較緊的upper bound是O(n)？
→ b10007034: 不是直接建一個AVL tree
→ b10007034: 給n個data，所以是O（nlogn）嗎？
→ b10007034: 順便問題目的意思，使不平衡變平衡，有這種演算法調整
→ b10007034: 嗎？類似heap的bottom-up法
推 FRAXIS: 先 inorder traverse 把元素存成 sorted array
→ FRAXIS: 然後 sorted array 轉 balanced tree
→ FRAXIS: 這樣作會使用額外 O(n) 的空間 不過實際上有其他方法可以
→ FRAXIS: O(n) 時間 O(1) 空間把 unbalnaced tree變成balanced tree
推 FRAXIS: 可以搜 Day–Stout–Warren algorithm
太神 那這樣 這題也沒問題了 感謝
推 sarsman: 推F大，受益良多XD
推 b10007034: 原來如此，又是一個thread bt應用嗎
→ b10007034: 謝f大，順便問有些題目出題者的想法，我記得有時候題
→ b10007034: 目的upper bound不夠緊，答案就會算錯
→ b10007034: 那像這種時候，這題的e到底可不可以算對呢？還是要寫
→ b10007034: 老師想看的答案？
推 FRAXIS: 我想除了改考卷的人之外沒人可以回答這問題吧..
推 winiel559: 我認為選擇題就選對的，計算、簡答題才要寫tight的
→ winiel559: 我認為選擇題就選對的，計算、簡答題才要寫tight的
※ 編輯: 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