作者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