[理工] 107 電機丙 資結 幾題問題

看板Grad-ProbAsk作者 (Mistel)時間6年前 (2019/12/24 16:24), 6年前編輯推噓1(1推 0噓 12→)
留言13則, 2人參與, 6年前最新討論串1/1
https://www.ptt.cc/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://www.ptt.cc/bbs/Grad-ProbAsk/M.1577175862.A.BAC.html
推
12/24 16:36, 6年前 , 1F
4 我也寫false median用augmented AVL不是可以到logn
12/24 16:36, 1F
→
12/24 16:36, 6年前 , 2F
嗎 甚至直接用一個指標指 1by1給不就O(1)? 16E應該錯
12/24 16:36, 2F
→
12/24 16:36, 6年前 , 3F
的 splay會斜取 19我也有選a
12/24 16:36, 3F
splay分攤時間應該是logn？ 洪逸的筆記這樣寫的 ※ 編輯: mistel (114.136.184.208 臺灣), 12/24/2019 16:54:30
→
12/24 16:55, 6年前 , 4F
不過真要說heap的delete也可以分攤到O(1)，所以有時候真
12/24 16:55, 4F
→
12/24 16:55, 6年前 , 5F
不知道台大到底該答什麼...
12/24 16:55, 5F
→
12/24 16:56, 6年前 , 6F
worst case是O(n)
12/24 16:56, 6F
→
12/24 16:58, 6年前 , 7F
我看到了 感謝你
12/24 16:58, 7F
→
12/24 17:01, 6年前 , 8F
沒事 worst case也要用amortized 是我錯了
12/24 17:01, 8F
→
12/24 17:13, 6年前 , 9F
12/24 17:13, 9F
→
12/24 17:15, 6年前 , 10F
不過感覺怪怪的 worst是O(n)然後又amortized ...
12/24 17:15, 10F
→
12/25 12:14, 6年前 , 11F
我看其他網站寫O(n) worst case，不知道聖經本寫什麼：（
12/25 12:14, 11F
→
12/25 12:43, 6年前 , 12F
我看題庫班 洪逸也是寫ABCD worst case 還是O(n)啦
12/25 12:43, 12F
→
12/25 12:43, 6年前 , 13F
但維基把他amortized了= =
12/25 12:43, 13F
‣ 更多 mistel 的文章
文章代碼(AID): #1U0Siski (Grad-ProbAsk)