[理工] 109 台大電機丙資演 fibonacci heap

看板Grad-ProbAsk作者waes81224 (changchang)時間3年前 (2021/01/25 20:30)推噓2(2推 0噓 1→)

留言3則, 2人參與討論串1/1

https://i.imgur.com/yNVJXsL.jpg

想問9 11你們會怎麼選擇我查 Horowitz 寫的DS 他提到在 Delete Min 以及 Decrease Key時 Worst case 跟 amortized的time complexity不一樣 https://i.imgur.com/y8ykvvj.jpg

9. 他問worst case 下的 one decrease-key 是要取 O(n)嗎？而不是取 amortized的O(logn) 11. 他問 worst case 下 n次 decrease-key 則是要取 amortized O(logn)*n=O(nlogn) 而不是取 O(n)*n=O(n^2) 這樣的想法可以嗎？有點被 worst case 以及amortized 搞亂了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 119.77.140.137 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1611577832.A.E44.html

推

jordan1997

01/25 20:44, 3年前 , 1^F

01/25 20:44, 1^F

→

jordan1997

01/25 20:44, 3年前 , 2^F

01/25 20:44, 2^F

推

mathtsai

01/25 22:13, 3年前 , 3^F

01/25 22:13, 3^F