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

[waes81224 (changchang)]

 
 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: 我覺得如果題目問n次operation 的話用（amortized cos
→ jordan1997: t ）*n，而單一的就直接看worst case 是多少，
推 mathtsai: 單一: worst case 多次操作: amortized
感謝兩位大大
所以如果只問單次就找worst case
問n次 就找amortized cade
 
※ 編輯: waes81224 (119.77.140.137 臺灣), 01/26/2021 11:37:25