提取民的最大時間 - 斐波那契堆

Question

什麼是n - 元素斐波那契堆執行extract-min的實際最大時間？

是否O(D(n) + t(H))，其中D(n) = lg*n是節點的最大度在正元件堆和t(H) = O(n)是一個數字在堆ħ根？

這是否意味着答案問題其實上面O(n) = Theta(n)？如果不是，請糾正我的想法和答案。

Answer 1

你是正確的 - 一個單一的電話來deleteMin最大時間複雜度爲O(n)。操作上的下限O(logn)是其攤銷時間複雜度，並且在最佳情況和最壞情況之間是相同的。