作者waes81224 (changchang)
看板Grad-ProbAsk
标题[理工] 109 台大电机丙 资演 fibonacci heap
时间Mon Jan 25 20:30:30 2021
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1611577832.A.E44.html
1F：推 jordan1997: 我觉得如果题目问n次operation 的话用（amortized cos01/25 20:44
2F：→ jordan1997: t ）*n，而单一的就直接看worst case 是多少，01/25 20:44
3F：推 mathtsai: 单一: worst case 多次操作: amortized01/25 22:13
感谢两位大大
所以如果只问单次就找worst case
问n次 就找amortized cade
※ 编辑: waes81224 (119.77.140.137 台湾), 01/26/2021 11:37:25