[理工] [資結]關於fibonacci heap的decrease-key
關於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
→
06/28 10:51, , 1F
06/28 10:51, 1F
→
06/28 11:52, , 2F
06/28 11:52, 2F
→
06/28 11:53, , 3F
06/28 11:53, 3F
謝謝，已經問到答案
fibonacci heap通常由link list實作
所以跟link list的delete操作一樣
假設該node的pointer已知（由其他演算法來實現）
※ 編輯: shownlin (117.19.82.98), 06/28/2017 11:59:32
推
06/28 11:57, , 4F
06/28 11:57, 4F
→
06/28 11:59, , 5F
06/28 11:59, 5F
→
06/28 11:59, , 6F
06/28 11:59, 6F
→
06/28 12:00, , 7F
06/28 12:00, 7F