[理工] 資結 Fibonacci heap delete x
作者: q5332159 (chiu) 2018-10-31 15:46:00
關於delete x的時間
查了一下之後的理解是
因為要先decrease到最小再delete-min
所以是O(log n) (delete-min時merge的時間)
但是筆記下方又寫如果不是min的話採lazy merge
這樣為什麼還需要O(log n)呢?
謝謝各位～
作者: alan23273850 2018-10-31 16:50:00
所以按照你的說法，取兩個case比較久的那個，就還是O(lgn)阿，這是複雜度定義
作者: q5332159 (chiu) 2018-10-31 21:43:00
了解～還有一個問題就是delete x到底需不需要merge到不同高度 還是lazy就好？因為查到的是不管是刪最小或任意數都還是會做到delete-min 這個動作 那不就不lazy了嗎