[理工] 109台大電信資演兩題

[gj94jo3a12 (NTUWayne)]

1.
https://i.imgur.com/qS6Luo4.jpg

Splay tree 的worst case為O(n) Amortized cost為O(logn)
所以B D選項是O(n)還是O(logn)？
這題的答案又是什麼呢？


2.
https://i.imgur.com/LS7nYzH.jpg
https://i.imgur.com/dc0EZGv.jpg

Fib heap的操作 不是很確定 我寫AD

其中AB選項我是這樣寫有錯請指正
https://i.imgur.com/gUp2NM2.jpg


手機排版 很亂抱歉



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.77.146.10 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1610780863.A.FAD.html
※ 編輯: gj94jo3a12 (42.77.146.10 臺灣), 01/16/2021 15:08:46
推 kopk159: 2.b 59->40 樹沒變化吧
推 joywilliamjo: 他worat case amortized cost也是O(logn)啊，我覺得
→ joywilliamjo: 1 BD都對欸
→ gj94jo3a12: 2b 沒變化才對 感謝提醒
→ gj94jo3a12: 所以才不確定1.是要用單一worst case O(n)還是amortiz
→ gj94jo3a12: ed costO(logn)
推 asd597326: 借問 所以台大的splay都要考慮amortized case嗎