Mic*_*cio 2 algorithm big-o time-complexity data-structures fibonacci-heap
斐波那契堆在摊销意义上是有效的，但在最坏的情况下它们的效率如何？具体来说，在 n 节点斐波那契堆上，这些操作中的每一个的最坏情况时间复杂度是多少？
Fibonacci 堆上的 find-min 操作总是需要最坏情况的 O(1) 时间。总是有一个指针直接指向那个对象。
在最坏的情况下，最小删除的成本需要时间 Θ(n)。要看到这一点，请想象一下从一个空堆开始并对其进行一系列 n 次插入。每个节点都将存储在它自己的树中，并且执行删除最小堆会将所有这些对象合并为 O(log n) 棵树，需要 Θ(n) 工作来访问所有节点至少一次。
插入的成本是最坏情况 O(1)；这只是创建一个节点并将其添加到列表中。合并同样是 O(1)，因为它只是将两个列表拼接在一起。
在最坏情况下，减少键的成本是 Θ(n)。可以构建一个退化的斐波那契堆，其中所有元素都存储在由 n 个标记节点的链表组成的单个树中。在最底部的节点上做一个减少键然后触发一系列级联切割，将树转换为 n 个独立节点。