作者assassin88 (AI)
看板Grad-ProbAsk
标题[理工] [DS]-台大95-资工所
时间Fri Jan 15 00:11:02 2010
《资料结构》 洪逸 P.9-74
Which of the following is true about the heap data structure ? n is node num.
(a)Deleting the minimum element in a min-heap takes O(logn) time
(b)Finding the minimum element in a min-heap takes O(logn) time
(c)Inserting a node into a Fin. heap takes O(logn) time
(d)Decrease-key operation on a node of a Fib. heap takes O(1) time
(e)Finding both the monimum and the maximum elements in a min-max heap
takes O(1) time
答案是给(A)(C)(D)(E)，
可是我觉得答案有点问题，
(B)应该是O(1)
(C)应该是O(1)
(D)应该是O(logn)
答案是(A)(E)？
请指教..感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.57.78.8
※ 编辑: assassin88 来自: 61.57.78.8 (01/15 00:25)
1F：推 extremity:c的fin是？fib的话，insert是O(1)没错 01/15 01:37
2F：→ extremity:decrease key也是O(1)，可用Amortize证 01/15 01:38
3F：→ assassin88:C打错..是Fib. 没错~所以C是错的? 01/15 12:00
4F：→ assassin88:请问Amortize证明哪边有提到?? 01/15 12:01
5F：推 supergud:(C)in wrost case是O(logn) 大部分case和avg.才是O(1) 01/15 12:15
6F：→ supergud:题目没说是一般情形 所以有可能是worst case 01/15 12:16