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

看板Grad-ProbAsk作者時間8年前 (2017/12/23 23:18), 8年前編輯推噓13(13推 0噓 23→)
留言36則, 6人參與, 8年前最新討論串1/1
請教一下各位大大對於這兩題的看法 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
→
12/23 23:47, 8年前 , 1F
覺得第一題是指樹高,false(三個點的時候)
12/23 23:47, 1F
推
12/24 06:17, 8年前 , 2F
這些是多選題嗎？
12/24 06:17, 2F
上面是 是非 下面是 多選 ※ 編輯: jerry900287 (61.230.131.29), 12/24/2017 09:42:53
推
12/24 11:11, 8年前 , 3F
12 abc 都不對 d 是對的
12/24 11:11, 3F
→
12/24 11:12, 8年前 , 4F
e 的話是 O(n) 那題目寫 O(n log n) 應該也沒錯？
12/24 11:12, 4F
推
12/24 11:47, 8年前 , 5F
12.A的機率要怎麼算啊@@
12/24 11:47, 5F
推
12/24 11:54, 8年前 , 6F
你只要考慮 n = 2^k - 1 的情況 隨機插入變成 perfect
12/24 11:54, 6F
→
12/24 11:54, 8年前 , 7F
balanced search tree 機率非常非常小..
12/24 11:54, 7F
→
12/24 12:10, 8年前 , 8F
12 (b) amortized的情況下為什麼不是O(log n) ?
12/24 12:10, 8F
推
12/24 12:28, 8年前 , 9F
expected 是 O(log n), amortized 應該不會是O(log n)
12/24 12:28, 9F
→
12/24 12:29, 8年前 , 10F
因為 amortized 是指一連串的 operation 的 worst case
12/24 12:29, 10F
→
12/24 12:30, 8年前 , 11F
執行時間 隨機插入的話 有 > 0 的機率 樹會非常不平衡
12/24 12:30, 11F
→
12/24 12:30, 8年前 , 12F
所以 amortized 沒辦法是 O(log n)
12/24 12:30, 12F
推
12/24 15:29, 8年前 , 13F
第一題我寫true,找不到反例，有大大可以找出個反例嗎 感
12/24 15:29, 13F
→
12/24 15:29, 8年前 , 14F
謝
12/24 15:29, 14F
→
12/24 16:24, 8年前 , 15F
如果題目指的是樹高，這應該是反例
12/24 16:24, 15F
→
12/24 16:24, 8年前 , 16F
如果是執行時間AVL Tree應該會快一些
12/24 16:24, 16F
→
12/24 16:24, 8年前 , 17F
12/24 16:24, 17F
OK 那第一題應該沒問題了 謝謝你
推
12/24 17:54, 8年前 , 18F
e 為什麼比較緊的upper bound是O(n)？
12/24 17:54, 18F
→
12/24 17:54, 8年前 , 19F
不是直接建一個AVL tree
12/24 17:54, 19F
→
12/24 17:54, 8年前 , 20F
給n個data，所以是O（nlogn）嗎？
12/24 17:54, 20F
→
12/24 17:56, 8年前 , 21F
順便問題目的意思，使不平衡變平衡，有這種演算法調整
12/24 17:56, 21F
→
12/24 17:56, 8年前 , 22F
嗎？類似heap的bottom-up法
12/24 17:56, 22F
推
12/24 20:30, 8年前 , 23F
先 inorder traverse 把元素存成 sorted array
12/24 20:30, 23F
→
12/24 20:30, 8年前 , 24F
然後 sorted array 轉 balanced tree
12/24 20:30, 24F
→
12/24 20:30, 8年前 , 25F
這樣作會使用額外 O(n) 的空間 不過實際上有其他方法可以
12/24 20:30, 25F
→
12/24 20:31, 8年前 , 26F
O(n) 時間 O(1) 空間把 unbalnaced tree變成balanced tree
12/24 20:31, 26F
推
12/24 20:34, 8年前 , 27F
可以搜 Day–Stout–Warren algorithm
12/24 20:34, 27F
太神 那這樣 這題也沒問題了 感謝
推
12/24 21:36, 8年前 , 28F
推F大，受益良多XD
12/24 21:36, 28F
推
12/25 09:33, 8年前 , 29F
原來如此，又是一個thread bt應用嗎
12/25 09:33, 29F
→
12/25 09:35, 8年前 , 30F
謝f大，順便問有些題目出題者的想法，我記得有時候題
12/25 09:35, 30F
→
12/25 09:36, 8年前 , 31F
目的upper bound不夠緊，答案就會算錯
12/25 09:36, 31F
→
12/25 09:37, 8年前 , 32F
那像這種時候，這題的e到底可不可以算對呢？還是要寫
12/25 09:37, 32F
→
12/25 09:37, 8年前 , 33F
老師想看的答案？
12/25 09:37, 33F
推
12/25 10:31, 8年前 , 34F
我想除了改考卷的人之外沒人可以回答這問題吧..
12/25 10:31, 34F
推
12/25 11:12, 8年前 , 35F
我認為選擇題就選對的，計算、簡答題才要寫tight的
12/25 11:12, 35F
→
12/25 11:12, 8年前 , 36F
我認為選擇題就選對的，計算、簡答題才要寫tight的
12/25 11:12, 36F
※ 編輯: 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
‣ 更多 jerry900287 的文章
文章代碼(AID): #1QFdFK8A (Grad-ProbAsk)