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

看板Grad-ProbAsk作者 (NTUWayne)時間3年前 (2021/01/16 15:07), 3年前編輯推噓2(2推 0噓 4→)
留言6則, 3人參與, 3年前最新討論串1/1
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
推
01/16 19:14, 3年前 , 1F
2.b 59->40 樹沒變化吧
01/16 19:14, 1F
推
01/16 19:40, 3年前 , 2F
他worat case amortized cost也是O(logn)啊，我覺得
01/16 19:40, 2F
→
01/16 19:40, 3年前 , 3F
1 BD都對欸
01/16 19:40, 3F
→
01/16 19:53, 3年前 , 4F
2b 沒變化才對 感謝提醒
01/16 19:53, 4F
→
01/16 19:54, 3年前 , 5F
所以才不確定1.是要用單一worst case O(n)還是amortiz
01/16 19:54, 5F
→
01/16 19:54, 3年前 , 6F
ed costO(logn)
01/16 19:54, 6F
‣ 更多 gj94jo3a12 的文章
文章代碼(AID): #1W0f2_-j (Grad-ProbAsk)