第11章 均摊分析

关键词 均摊界分析

在这一章，我们会分析在第4章和第6章里介绍过的若干种高级数据结构的运行时间，比如伸展树、平衡树、队列、堆等。

在这一章，我们会分析M个操作序列中的任意序列的最坏情形运行时间，这跟之前的单个操作的最坏情形分析是不一样的。

虽然AML树的标准树操作中的每个操作的最坏运行时间为，但是实现AML树有点复杂，不仅是因为要考虑多种情形，而且是因为需要正确地维护和更新树的平衡信息。使用AVL树的原因是因为在非平衡树上执行个操作序列时，可能某个序列会花费时间，这个代价很高。而且，非平衡树的主要问题是这种情形可能会重复出现。

伸展树提供了一种令人满意的替代方案。虽然伸展树的每个操作仍需花费时间，但是前述退化现象(执行个操作序列时可能出现某个操作花费)不会在伸展树中重复出现，而且可以证明在伸展树中，从整体上看，M个操作中的任一序列花费的最坏时间为。长期运行下来，伸展树的每个操作花费的时间为。这就是伸展树的均摊时间上界。

均摊上界比最坏情形上界更弱，因为均摊界不是对任一单个操作都成立的。因为单次操作不满足均摊界不重要，所以如果既能保留操作序列的上界和又能简化数据结构的话，那么我们就愿意牺牲单次操作的上界。

均摊上界比等价的平均情形上界更强，比如二叉搜索树的每个操作花费的平均情形时间为，二叉搜索树的M个序列花费的时间为。

由于推导均摊界需要处理整个序列，而不只是一个，则均摊分析是有技巧的。

本章的主要内容有：

• 分析二项式队列的操作；
• 分析偏斜堆的操作；
• 介绍和分析Fibonacci堆；
• 分析伸展树；