摊还分析（进阶）

复习

本章为进阶内容，零基础读者可以跳过，不影响后续阅读。

　　上一章我们把“最好、最坏、平均”分开了。这一章再介绍一种更精细的视角：摊还分析（amortized analysis）。它专门处理那种“平时很便宜，偶尔突然很贵”的操作。

　　先看那个经典例子：动态数组。

　　动态数组的容量是有限的。只要还有空位，往末尾追加一个元素就很便宜，是 O(1)。

　　可一旦装满了，就得扩容：申请一块更大的空间，把原来的元素全部复制过去，再追加新元素。这一次复制的代价，是 O(n)。

　　于是问题来了：这个数组的插入，到底是快还是慢？

　　关键在这里：如果我们每次扩容都把容量翻倍，那么每次昂贵的扩容之后，都要经过差不多同样多次的廉价插入，才会再次装满。

　　把这一连串操作合起来平均一下，昂贵的复制成本，就被分摊到了中间那许多次廉价插入上。算下来，平均每次插入的代价仍然是 O(1)。

　　这就是摊还的含义：不是看某一次操作有多贵，而是看一长串操作的总代价，平均到每一次是多少。偶尔的巨额开销，被大量的廉价操作“摊”平了。

　　可以这样记账：每次普通插入，除了完成插入，还悄悄“存”下一点信用；等扩容时，就用攒下的信用来支付那次昂贵的复制。总体一算，收支平衡。

　　这里必须划清界限：摊还分析不等于平均情况分析。

　　换句话说，摊还是一种确定性的保证，而不是统计期望。哪怕你运气极差、每次都刚好触发扩容，把总代价平均下来，依然不会超过摊还的界限。

　　所以，下次看到“单次 O(n)”和“摊还 O(1)”并存时，别觉得矛盾——它们说的是两件不同的事：一次有多坏，和一串平均有多好。

思考题 1

　　动态数组单次插入最坏是 O(n)，为什么还说它的插入摊还是 O(1)？

思考题 2

　　摊还分析和“平均情况”有什么不同？哪个更接近一种保证？

　　因为昂贵只在“扩容”那一次发生，而扩容后要经过许多次廉价插入才会再次扩容。把扩容成本分摊到这些廉价操作上，平均每次的代价仍是常数级。所以单次最坏是 O(n)，摊还却是 O(1)。

　　平均情况依赖对输入分布的假设，是一种统计期望；摊还分析则不做任何概率假设，保证的是任意一串操作的总代价都在界限之内。因此，摊变更接近一种确定性的保证，而不是赌博式的期望。

设计师 | 南国微雪