[理工] [資結]關於fibonacci heap的decrease-key

[shownlin (哈哈阿喔)]

關於fibonacci heap的兩個動作
delete x Time:O(log n)
decrease-key Time:O(1)
想問這兩種操作的時間複雜度是如何得來的
因為要做兩種操作前不是應該先search嗎
既然有search的動作那O(1)不就不太合理了？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 117.19.82.98
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1498617121.A.16D.html
→ s89162504: amortize
→ shownlin: 平均我知道，但是search應該是每次必要的？
→ shownlin: 請問search的時間怎麼算？ 也是常數時間嗎
謝謝，已經問到答案
fibonacci heap通常由link list實作
所以跟link list的delete操作一樣
假設該node的pointer已知（由其他演算法來實現）
※ 編輯: shownlin (117.19.82.98), 06/28/2017 11:59:32
推 FRAXIS: 應該是已經給定 node 然後作 delete/decrease-key
→ FRAXIS: 所以就不用 search 了 而且 priority queue 也沒辦法
→ FRAXIS: 有效率的 search
→ shownlin: 對XD，謝謝樓上