[理工] [資結]關於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，謝謝樓上

繼續閱讀