平摊分析(Amortized Analysis)将数据结构的不同操作放到一起来考虑,而不是仅对某种操作的单一考虑。在平摊分析中,不会涉及概率问题。平摊分析可以用来证明,在一系列操作中,即使某个操作代价很大,但平均代价仍是很小的。本文记录三种平摊分析最常用的技术。

聚集分析(Aggregate analysis)

在聚集分析中,要证明n个操作(可以是不同种类的操作)构成的操作序列在最坏情况下用时T (n),因此每个操作的平均时间为T(n)/n,在平摊分析中,平均代价被指派为平摊代价。看下面一个栈操作的实例。

对于栈操作,PUSH,POP的时间复杂度都是O(1)。我们给栈添加一种新的操作——MULTIPOP(S,k),如果栈中对象足够,它会出栈k个对象,否则弹出栈中全部对象。这个操作的复杂度为O(n)。其伪码如下:

1
2
3
4
MULTIPOP(S, k)
while not STACK-EMPTY(S) and k ≠ 0
do POP(S)
k = k - 1

由PUSH, POP, 和 MULTIPOP构成的一个长度为n的序列操作作用在一个空栈上,
最坏情况下的时间复杂度为多少?当然,你可以说是\(O(n^2)\)。的确没错,毕
竟这一序列操作可由n个MULTIPOP组成,由此得出\(O(n)*n = O(n^2)\)。但
我们还能将这个上限向下压。

MULTIPOP的复杂度为O(n),但它真实的时间花费其实是由伪码中第2句决定的
——MULTIPOP内部执行了多少次POP操作。当我们把上述问题综合考虑的时候,问题
出现了戏剧性的转变。对于一个空栈来说,调用POP的操作最多等于PUSH的操作。可
见上述的n个操作可以有更矮的上界O(n)。而三种操作的平摊代价为
\(O(n) / n = O(1)\)。

记账方法(The accounting method)

在记账方法中,给不同的操作分配不同的平摊代价。有些操作的平摊代价大于实际代价,就把多余的部分当作存款,供那些实际代价大于平摊代价的操作使用。需要保证的是序列操作的平均代价总和应该要不小于实际代价的总和。仍然用上面栈的例子,我们给栈的三种操作分派的平摊代价如下:

PUSH        2,
POP         0,
MULTIPOP    0.

这是什么意思呢?假设我们把栈数据结构看做餐厅叠放一堆盘子,每次压盘子入栈需要付费1美元,弹出盘子也需要1美元。但是如果我放盘子的时候付费2美元,1美元用来支付入栈的费用,另1美元放在盘子上,告诉收钱的家伙,如果弹出盘子的时候,盘子上的那一美元就是付盘子弹出的费用。这样事情就简单了,任何出栈相关的花费都可以看为0,因为每一个盘子进栈的时候已经预付了足够它出栈的费用。所以POP和MULTIPOP都可以指派平摊代价为0.

所以由PUSH, POP, 和 MULTIPOP构成的一个长度为n的序列操作作用在一个空栈上的总平摊代价为O(n),而它的实际代价也是。

势能方法(he potential method)

势能方法其实与记账方法相通,不同之处在于势能方法不是把账记在单个的对象上,而是记
全记在数据结构上。当然按书上的说法来讲就是“势”,当某个操作支付的多时可以为这个数
据结构积蓄势能,积蓄的势能则可以释放来支付后续的操作。

势能方法的工作流程如下. 对一个初始的数据结构\( D_0 \)执行n次操作。用\( D_i \)
来表示执行第i次操作后的数据结构。函数\( \Phi(D_i) \)代表数据结构\(D_i\)
拥有的势能。如果用\( c_i \)表示第i个操作的实际代价的话,那第i步操作的平摊
代价就相当于实际代价加上由于这一步操作所增加的势能。所以第i步操作的平摊代价:
公式1

n 步操作的总平摊代价则为:

公式2

如果使得\( \Phi(D_n) \geq \Phi(D_0) \)为真,那么我们就可以用总的平摊代价
公式3表示总的实际代价公式4的一个上界。

再次用上面的栈例子作为实例,一开始时空栈,而且\( \Phi(D_0) = 0 \)(势能为0)。
于是有\( \Phi(D_n) \geq \Phi(D_0) = 0 \)。因n的大小是不确定的,这个表达式
要说明的是在一系列操作的过程中,势能可以有增有减,但绝不能为负数。

如果第i个操作是个PUSH操作,那么第i个操作带来的势差为:
\( \Phi(Di) - \Phi(D{i-1} = (s + 1) - s = 1) \)。那么平摊代价PUSH操作的
平摊代价就为:

![公式5][fromula5]

同理也可以求得POP操作的平摊代价为0.

如果第i步操作为MULTIPOP(S, k)。令k’= min(k,s)[^注1],其中s表示栈
中元素的个数。那么\( \Phi(Di) - \Phi(D{i-1} = -k’) \)。它的平摊代价就为:

公式6

[^注1]: 在这儿k’= min(k,s),直接表达的意思是不能令栈中的对象数目为负,而就势能方法来说,它表述了一点原则就是,这一次操作不能令栈的势能为负。