algorithm - Extract-Min 的最大时间 - 斐波那契堆

Question

extract-min在n-element Fibonacci heap上执行的实际最长时间是多少？

是， n 元素堆中节点的最大度数在O(D(n) + t(H))哪里，堆 H 中的根数是多少？D(n) = lg*nt(H) = O(n)

这是否意味着上述问题的答案实际上是O(n) = Theta(n)？如果不是，请纠正我的想法并回答。

Answer 1

你是对的——单次调用的最大时间复杂度deleteMin是O(n). 该操作的下限O(logn)是其摊销时间复杂度，并且在最佳情况和最坏情况之间是相同的。