[理工] [资结]关于fibonacci heap的decrease-key shownlin PTT批踢踢实业坊

楼主: shownlin (哈哈阿喔) 2017-06-28 10:31:58

关于fibonacci heap的两个动作
delete x Time:O(log n)
decrease-key Time:O(1)
想问这两种操作的时间复杂度是如何得来的
因为要做两种操作前不是应该先search吗
既然有search的动作那O(1)不就不太合理了？

作者: s89162504 (阿本) 2017-06-28 10:51:00

amortize

楼主: shownlin (哈哈阿喔) 2017-06-28 11:52:00

平均我知道，但是search应该是每次必要的？请问search的时间怎么算？也是常数时间吗

作者: FRAXIS (喔喔) 2017-06-28 11:57:00

应该是已经给定 node 然后作 delete/decrease-key所以就不用 search 了而且 priority queue 也没办法有效率的 search

楼主: shownlin (哈哈阿喔) 2017-06-28 12:00:00

对XD，谢谢楼上

继续阅读