作者assassin88 (2010)
看板Grad-ProbAsk
標題[理工] [DS]-Binomial heap
時間Sun Feb 7 21:54:24 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
1F：→ taitin:F-heap 跟 B-heap的delete都是 O(logn) 02/07 22:27
2F：→ taitin:B-heap的 amotizedDecrease-key O(logn) 02/07 22:27
3F：→ assassin88:這個好難判斷..到底什麼時候要用amortize分析? 02/07 22:46
4F：推 taitin:有很多operation的時候 02/07 22:49
5F：→ assassin88:所以只有這兩個需要更改嘛!? 02/07 23:15
6F：推 taitin:恩 02/07 23:29
7F：推 FRAXIS:Fibonacci Heap的Decrease Key是O(1)吧 02/07 23:39
8F：→ taitin:他應該是指amotized前後 02/07 23:44
9F：→ assassin88:恩恩~對..抱歉沒註明 02/07 23:54