作者mistel (Mistel)
看板Grad-ProbAsk
標題[理工] 107 電機丙 資結 幾題問題
時間Tue Dec 24 16:24:20 2019
https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1548751851.A.8FB.html
可參考前人的文章有一些討論
附上對來的答案：
https://i.imgur.com/gyvk583.jpg
請問
https://i.imgur.com/zJ5xLqG.jpg
第4題要keep track中位數就只能用遞迴的那個演算法嗎？
https://i.imgur.com/Gy4b0nR.jpg
請問第八題的t()是怎麼維持的？看不懂之前的文章
https://i.imgur.com/0ONY1uc.jpg
請問這題a選項為什麼錯？
感謝大家
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.184.208 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1577175862.A.BAC.html
1F：推 jeremyyuan: 4 我也寫false median用augmented AVL不是可以到logn12/24 16:36
2F：→ jeremyyuan: 嗎 甚至直接用一個指標指 1by1給不就O(1)? 16E應該錯12/24 16:36
3F：→ jeremyyuan: 的 splay會斜取 19我也有選a12/24 16:36
splay分攤時間應該是logn？ 洪逸的筆記這樣寫的
※ 編輯: mistel (114.136.184.208 臺灣), 12/24/2019 16:54:30
4F：→ mistel: 不過真要說heap的delete也可以分攤到O(1)，所以有時候真 12/24 16:55
5F：→ mistel: 不知道台大到底該答什麼... 12/24 16:55
6F：→ jeremyyuan: worst case是O(n) 12/24 16:56
7F：→ mistel: 我看到了 感謝你 12/24 16:58
8F：→ jeremyyuan: 沒事 worst case也要用amortized 是我錯了 12/24 17:01
10F：→ jeremyyuan: 不過感覺怪怪的 worst是O(n)然後又amortized ... 12/24 17:15
11F：→ mistel: 我看其他網站寫O(n) worst case，不知道聖經本寫什麼：（ 12/25 12:14
12F：→ jeremyyuan: 我看題庫班 洪逸也是寫ABCD worst case 還是O(n)啦 12/25 12:43
13F：→ jeremyyuan: 但維基把他amortized了= = 12/25 12:43