问为什么我们要对斐波那契堆做摊销分析？

EN

在二项式堆中，每个操作都保证以某种最坏情况下的性能运行。插入的时间永远不会超过O(log )，合并的时间永远不会超过O(log + log )，等等。因此，在分析二项式堆的效率时，通常会使用更传统的算法分析。

现在，也就是说，二项式堆的几个属性只有在进行分期分析时才会变得明显。例如，假设堆最初是空的，对一个二项式堆进行n次连续插入的开销是多少？您可以证明，在这种情况下，一次插入的摊销成本为O(1)，这意味着执行n次插入的总成本为O(n)。从这个意义上说，在传统分析的基础上使用摊销分析，可以比最初更保守的最坏情况分析揭示更多关于数据结构的见解。

在某种意义上，斐波那契堆最好的分析方式是分期，因为即使许多操作的最坏情况的界限并不是那么好(例如，在最坏的情况下，delete-min或delete key可能需要时间Θ(n) )，但是对于任何一系列操作，斐波那契堆都具有出色的分期性能。尽管单个删除分钟可能需要Θ(n)时间，但一系列m次删除分钟花费的时间永远不会超过Θ( more )时间。

然而，在另一种意义上，斐波那契堆被特别设计为在摊销意义上是有效的，而不是在最坏情况意义上。它们最初的发明是为了加速Dijkstra和Prim的算法，其中最重要的是在n节点堆上执行m个减键和n次删除的总成本，由于这是设计目标，因此设计者没有试图在最坏的情况下使Fibonacci堆高效。