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

作者: waes81224 (waes81224)   2021-01-25 20:30:30
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 搞亂了
作者: jordan1997 (allenwalker)   2021-01-25 20:44:00
我覺得如果題目問n次operation 的話用(amortized cost )*n,而單一的就直接看worst case 是多少,
作者: mathtsai (mathtsai)   2021-01-25 22:13:00
單一: worst case 多次操作: amortized

Links booklink

Contact Us: admin [ a t ] ucptt.com