[理工] [DS]-Binomial heap

[assassin88 (2010)]

因為有所謂的amortized，所以時間複雜度會改變，

因此想確認一下時間複雜度有沒有錯：

                 基本        amotized      Fibnacci heap
Insertion        O(1)          O(1)            O(1)

Delete-Min      O(logn)          ?             O(1)

Find-Min         O(1)          O(1)            O(1)

Merge            O(1)          O(1)            O(1)

Decrease-key    O(logn)        O(1)         O(logn)/O(1)

麻煩指導了~感謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.57.105.163
→ taitin:F-heap 跟 B-heap的delete都是 O(logn)
→ taitin:B-heap的 amotizedDecrease-key O(logn)
→ assassin88:這個好難判斷..到底什麼時候要用amortize分析?
推 taitin:有很多operation的時候
→ assassin88:所以只有這兩個需要更改嘛!?
推 taitin:恩
推 FRAXIS:Fibonacci Heap的Decrease Key是O(1)吧
→ taitin:他應該是指amotized前後
→ assassin88:恩恩~對..抱歉沒註明