algorithm - Fibonacci 堆上每个操作的最坏情况时间界限是多少？

Question

斐波那契堆在摊销的意义上是高效的，但在最坏的情况下它们的效率如何？具体来说，在 n 节点斐波那契堆上，这些操作中的每一个的最坏情况时间复杂度是多少？

• 找到分钟
• 删除分钟
• 插入
• 减少键
• 合并

Answer 1

Fibonacci 堆上的 find-min 操作总是需要最坏情况下的 O(1) 时间。始终维护一个直接指向该对象的指针。

在最坏的情况下，delete-min 的成本需要时间 Θ(n)。要看到这一点，请想象从一个空堆开始并向其中执行一系列 n 次插入。每个节点都将存储在它自己的树中，并且在堆中执行 delete-min 会将所有这些对象合并到 O(log n) 树中，需要 Θ(n) 工作至少访问所有节点一次。

插入的成本是最坏情况下的 O(1)；这只是创建一个节点并将其添加到列表中。合并的复杂度为 O(1)，因为它只是将两个列表拼接在一起。

在最坏的情况下，减少 key 的成本是 Θ(n)。可以构建一个退化的斐波那契堆，其中所有元素都存储在一棵树中，该树由 n 个标记节点的链表组成。在最底部的节点上执行减少键，然后触发一系列级联切割，将树转换为 n 个独立的节点。