平摊分析
在平摊分析中，执行一系列数据结构操作所需要的时间是通过对执行的所有操作求平均而得出的。平摊分析可用来证明在一系列操作中，即使单一的操作具有较大的代价，通过对所有操作求平均后，平均代价还是很小的。平摊分析与平均情况分析的不同之处在于它不牵涉到概率。这种分析保证了在最坏情况下每个操作具有平均性能。
本文将讨论平摊分析技术中最常用的三种技术：
- 聚集方法 —— 可以用这种方法确定一个n个操作的序列的总代价的上界T(n)。每个操作的平摊代价可表示为T(n)/n；
- 会计方法 —— 用它可确定每个操作的平摊代价。当有一种以上的操作时，每种操作都可有一个不同的平摊代价。这种方法对操作序列中的某些操作先“多记帐”，将多记的部分作为对数据结构中的特定对象上预付的存款存起来。在该序列中稍后要用到这些存款以补偿那些对它们记的“帐”少于其实际代价的操作。
- 势能方法 —— 它与会计方法的相似之处在于要确定每个操作的代价，且先对某些操作多记帐以补偿以后的不足记帐。这种方法将存数作为数据结构的“势能”来维护，而不是将存款与数据结构中的单个对象联系起来。
我们将用两个例子来说明这三个模型。第一个例子是个栈，它有一个新的操作MULTIPOP，它可一次弹出几个对象。另一个例子是个二进计数器，它利用操作INCREMENT从0开始计数。
在阅读本文时，读者应记住在平摊分析中所记的“帐”只是为了分析之用，它们不应出现在代码中。例如，当在采用会计方法时，如果将一存款赋予一个对象，在代码中就没有必要对其属性credit[x]赋一个相应的值了。
通过做平摊分析而获得的对某种数据结构特性的认识有助于优化设计。例如，后文中我们将用势能方法来分析一个动态扩充和收缩的表。
聚集方法
在平摊分析的聚集方法中，我们要证明对所有的n，n个操作构成的序列在最坏情况下总的时间为T(n)。在最坏情况下，每个操作的平摊代价就为T(n)/n。请注意这个平摊代价对每个操作都是成立的，即使当序列中存在几种类型的操作时也是一样的。后文中要研究的另两种方法—— 会计方法和势能方法——对不同类型的操作则可能赋予不同的平摊代价。
栈操作
在关于聚集方法的第一个例子中，我们要来分析增加了一个新操作的栈。我们知道，栈的两种基本操作 ——PUSH和POP，每个的时间代价都是O(1)：
- PUSH(S,x) —— 将对象x压入栈S；
- POP(S) —— 弹出并返回S的顶端元素；
因为这两个操作的运行时间都为O(1)，故我们可把每个操作的代价视为1。这样，一个n个PUSH和POP操作的序列的总代价就为n，而这n个操作的实际运行时间就为O(n)。
如果再增加一个栈操作MULTIPOP(S,k)，则情况会变得更有趣。该操作去掉S的k个顶端对象，或当它包含少于k个对象时弹出整个栈。在下面的伪代码中，如果当前栈中没有对象则操作STACK-EMPTY返回TRUE，否则它返回FALSE。
MULTIPOP(S,k)1 while not STACK-EMPTY(S) and k≠02 do POP(S)3 k ← k-1图1演示了MULTIPOP的一个例子，初始情况见图1(a)。最上面的四个对象由MULTIPOP(S,4)弹出，其结果如(b)中所示。下一个操
作是MULTIPOP(S,7)，它将栈清空——如图1(c)中所示——因为余下的对象已经不足七个了。
图1 MULTIPOP作用于栈S上的动作
MULTIPOP(S，k)作用于一个包含s个对象的栈上的运行时间怎样呢？实际的运行时间与实际执行的POP操作数成线性关系，因而只要按PUSH和POP具有抽象代价1来分析MULTIPOP就是够了。代码中while循环执行的次数即从栈中弹比的对象数min(s,k)。对该循环的每一次执行，在第2行中都要调用一次POP。这样，MULTIPOP的总代价即址为 min(s,k)，而实际运行时间则为这个代价的一个线性函数。
现在来对作用于一个初始为空的栈上的n个PUSH，POP和MULTIPOP操作构成的序列作个分析。序列中一次MULTIPOP操作的最坏情况代价为O(n)，因为栈的大小至多为n。这样，任意栈操作的最坏情况时间就是O(n)，而n个操作的总代价就是O(n2)，因为MULTIPOP操作可能会有O(n)个，每个的代价为O(n)。虽然这个分析是正确的，但通过分析每个操作的最坏情况代价而得的O(n2)的结论却是不够准确的。
利用平摊分析中的聚集方法，我们可以或的一个考虑到了整个操作序列的更好的上界。事实上，虽然某一次MULTIPOP操作的代价可能较高，但作用于初始为空的栈上的任意一个包含n个PUSH，POP和MULTIPOP操作的序列的代价至多为O(n)。为什么会是这样呢？一个对象在每次被压入栈后至多被弹出一次。所以，在一个非空栈上调用POP的次数(包括在MULTIPOP内的调用)至多等于PUSH操作的次数，即至多为n。对任意的n值，包含n个PUSH，POP和MULTIPOP操作的序列的总时间为O(n)。据此，每个操作的平摊代价为：O(n)/n=O(1)。
我们想再一次强调一下，虽然我们已说明了每个栈操作的平均代价(或平均运行时间)为O(1)，但没有用到任何概率推理。实际上是给出了一列n个操作的最坏情况界O(n)。用n来除这个总代价即可得每个操作的平均代价(或说平摊代价)。
二进制计数器
作为聚集方法的另一个例子，考虑实现一个由0开始向上计数的k位二进制计数器的问题。我们用一个数组A[0..k-1](此处length[A]=k)作为计数器。存储在计数器中的一个二进数x的最低位在A[0]中，最高位在A[k-1]中，故
开始时，x=0，故A[i]=0，i=0,1,...,k-1。为将计数器中的值加1(模2k)，我们可用下面的过程：
INCREMENT(A)1 i←02 while i<length[A] and A[i]=13 do A[i]←04 i←i+15 if i<length[A]6 then A[i]←1这个算法与硬件实现的行波进位计数器基本上是一样的。图2演示了一个二进制计数器从0至16的16次增值的过程。发生翻转而取得下一个值的位都加了阴影。右边示出了位翻转所需的代价。注意总代价始终不超过INCREMENT操作总次数的两倍。在第2-4行中每次while循环的开始，我们希望在位置i处加1。如果A[i]=1，则加1后就将位置i处的数位置为0，并产生一个进位1，它在循环的下一次执行中加到位置i+1上；否则，循环结束；然后，如果i<k，我们知道A[i]=0，故将1加到位置i后，使0变为1，这在第6行中完成。每次INCREMENT操作的代价与被改变值的位数成线性关系。
像在栈的例子中一样，大致分析一下只能得到一个正确但不紧确的界。在最坏情况下， INCREMENT的每次执行要花O(k)时间，此时数组A中包含全1。这样，在最坏情况下，作用于一个初始为零的计数器上的n个INCREMENT操作的时间就为O(nk)。
如果我们分析得更精确一些的话，则可得到n次lNCREMENT操作的序列的最坏情况代价为O(n)。关键是要注意到在每次调用INCREMENT中，并不是所有的位都发生变化：作用于初始为零的计数器上的n次lNCREMENT操作导致A[1]变化了ë n/2 û次。类似地，位A[2]在n次INCREMENT操作中共变化ë n/4 û次。一般地，对i=0,1,..,ë ㏒n û，位A[i]在一个作用于初始为零的计数器上的n次INCREMENT操作的序列中共要翻转ë n/2i û次。对i > ë ㏒n û，位A[i]始终不发生变化。这样，在序列中发生的位翻转的总次数为
由此可知，作用于一个初始为零的计数器上的n次INCREMENT操作的最坏情况时间为O(n)，因而每次操作的平摊代价为O(n)/n=O(1)。
|
Counter |
A[7] |
A[6] |
A[5] |
A[4] |
A[3] |
A[2] |
A[1] |
A[0] |
Total |
||
|
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
|
2 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
3 |
|
|
3 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
4 |
|
|
4 |
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
7 |
|
|
5 |
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
8 |
|
|
6 |
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
10 |
|
|
7 |
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
11 |
|
|
8 |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
15 |
|
|
9 |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
16 |
|
|
10 |
|
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
18 |
|
|
11 |
|
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
19 |
|
|
12 |
|
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
22 |
|
|
13 |
|
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
23 |
|
|
14 |
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
25 |
|
|
15 |
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
26 |
|
|
16 |
|
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
31 |
|
图2 在16次INCREMENT操作作用下，一个八位二进制计数器的值从0变到16
会计方法
在平摊分析的会计方法中，我们对不同的操作赋予不同的费值，某些操作的费值比它们的实际代价或多或少。对每一操作所记的费值即其平摊代价。当一个操作的平摊代价超过了它的实际代价时，两者的差值就被作为存款赋给数据结构中一些特定的对象。存款可在以后用于补偿那些其平摊代价低于其实际代价的操作。这样，我们就可将一操作的平摊代价看作为两部分——实际代价与存款(或被储蓄或被使用)。这与聚集方法有很大不同，后者所有操作都具有相同的平摊代价。
在选择操作的平摊代价时是要非常小心的。如果我们希望通过对平摊代价的分析说明每次操作具有较小的最坏情况平均代价，则操作序列的总的平摊代价就必须是该序列的总的实际代价的一个上界。而且，像在聚集方法中一样，这种关系必须对所有的操作序列都成立。这样，与该数据结构相联系的存款始终应该是非负的，因为它表示了总的平摊代价超过总的实际代价的部分。如果允许总的存款为负的话(开始时对某些操作的费值记得过低)，则在某一时刻总的平摊代价就会低于总的实际代价。对到该时刻为止的操作序列来说，总的平摊代价就不会是总的实际代价的一个上界。所以，我们必须始终注意数据结构中的总存款不能是负的。
栈操作
为了说明平摊分析中的会计方法，我们再回过头看看栈的例子。各栈操作的实际代价为：
- PUSH 1
- POP 1
- MULTIPOP min(k,s)
其中k为MULTIPOP的一个参数，s为调用该操作时栈的大小。现对它们赋予以下的平摊代价：
- PUSH 2
- POP O
- MULTIPOP O
请注意MULTIPOP的平摊代价是个常数0，而它的实际代价却是个变量。此处所有的三个平摊代价都是O(1)，但一般来说所考虑的各种操作的平摊代价会渐近地变化。
现在我们来说明只需要用平摊代价就支付任何的栈操作序列。假设我们用1元钱来表示代价的单位。开始时栈是空的。栈数据结构与在餐馆中一堆迭放的盘子类似。当将一个盘子压入堆上时，我们用1元来支付该压入动作的实际代价，并有1元的存款(记的是2元的帐)，将该1元钱放在刚压入的盘子的上面。在任何一个时间点上，堆中每个盘子的上而都有l元钱的余款。
盘中所存的钱是用来预付将盘从栈中弹出所需代价的。当我们在执行了一个POP操作时，对该操作不用收任何费，只要用盘中所存放的余款来支付其实际代价即可。为弹出一个盘子，我们拿掉该盘子上的1元余款，并用它来支付弹出操作的实际代价。这样，在对PUSH操作多收了一点费后，就无需对POP操作收取任何费用。
更进一步，我们对MULTIPOP操作也无需收费。为弹出第一个盘子，我们取出其中的1元余款并用它支付一次POP操作的实际代价。为弹出第二个盘子，再取出该盘子上的1元余款来支付第二次POP操作，等等。这样，对任意的包含n次PUSH，POP和MULTIPOP操作的序列，总的平摊代价就是其总的实际代价的一个上界。又因为总的平摊代价为O(n)，故总的实际代价也为O(n)。
二进制计数器的增值
为进一步说明会计方法，我们再来分析一下作用于一个初始为0的二进制计数器上的INCREMENT操作。我们前面已经说过，这个操作的运行时间与发生翻转的位数是成正比的，而位数在本例中即为代价。我们还是用1元钱来表示位数代价(此例中即为某一位的翻转)。
为进行平摊分析，我们规定对将某一位置为1的操作收取2元的平摊费用。当某数位被设定后，我们用2元中的1元来支付置位操作的实际代价，而将另1元存在该位上作为余款。在任何时间点上，计数器中每个1上都有1元余款。这样在将某位复位成0时不用支付任何费用，只要取出该位上的1元余款即可。
现在就可以来确定INCREMENT的平摊代价了。在while循环中复位操作的代价是由有关位上的余款来支付的。在INCREMENT的第6行中至多有一位被复位，所以一次INCREMENT操作的代价至多为2元。又因为计数器中为1的位数始终是非负的，故其中总的余款额也是非负的。对n次INCREMENT操作，总的平摊代价为2n元，即O(n)，这就给出了总的实际代价的一个界。
势能方法
平摊分析中的势能方法不是将已预付的工作作为存储在数据结构特定对象中的存款来表示，而是表示成--种“势能”，或“势”，它在需要时可释放出来以支付后面操作的代价。势是与整个数据结构而不是其中的个别对象发生联系的。
势能方法的工作过程是这样：开始时先对一个初始数据结构D0执行n个操作，对每个i=1,2,..n，设ci为第i个操作的实际代价，Di为对数据结构Di-1作用第i个操作的结果。势函数F将每个数据结构Di映射为一个实数F(Di)，即与数据结构Di相联系的势。第i个操作的平摊代价定义为：
(1)
从这个式子可以看出，每个操作的平摊代价为其实际代价加上由于该操作所增加的势。根据等式(1)，n个操作的总的平摊代价为：
（2）
如果我们能定义--个势函数F使得F(Dn)≧F(D0)，则总的平摊代价就是总的实际代价的一个上界。在实践中，我们并不总是
知道要执行多少个操作，所以，如果要求对所有的i有F(Di)≧F(D0)，则就应像在会计方法中一样，保证预先支付。通常为了方便起见，我们定义F(D0)为0，然后再证明对所有i有F(Di)≧O；倘若F(D0)≠0，只要构造势函数F¢，使得F¢(i)=F(Di)-F(D0)即可。
从直觉上看，如果第i个操作的势差F(Di)-F(Di-1)是正的，则平摊代价
就表示对第i个操作多收了费，同时数据结构的势也随之增加了。如果势差是负的，则平摊代价就表示对第i个操作的不足收费，这时就可通过减少势来支付该操作的实际代价。
由等式(1)和(2)所定义的平摊代价依赖于所选择的势函数F，不同的势函数可能会产生不同的平摊代价，但它们都是实际代价的上界。在选择一个势函数时常要作一些权衡，可选用的最佳势函数的选择要取决于所需的时间界。
栈操作
为了说明势能方法，我们再一次来研究栈操作PUSH，POP和MULTIPOP。定义栈上的势函数F为栈中对象的个数。开始时我们要处理的是空栈D0，F(D0)=0。因为栈中的对象数始终是非负的，故在第i个操作之后的栈Di就具有非负的势，且有
以F表示的n个操作的平摊代价的总和就表示了实际代价的一个上界。
现在我们来计算各栈操作的平摊代价。如果作用于一个包含s个对象的栈上的第i个操作是个PUSH操作，则势差为
根据等式(1)，该PUSH操作的代价为
假设第i个操作是MULTIPOP(S,k)，且弹出了k'=min(k,s)个对象。该操作的实际代价为k'，势差为
这样，MULTIPOP操作的平摊代价为
类似地，POP操作的平摊代价也是0。
三种栈操作中每一种的平摊代价都是O(1)，这样包含n个操作的序列的总平摊代价就是O(n)。因为我们已经证明了F(Di)≧F(D0)，故n个操作的总平摊代价即为总的实际代价的一个上界。这样n个操作的最坏情况代价为O(n)。
二进制计数器的增值
作为说明势能方法的另一个例子，我们再来看看二进计数器的增值问题。这---次，我们定义在第i次INCREMENT操作后计数器的势为bi，即第i次操作后计数器中1的个数。
我们来计算一下一次INCREMENT操作的平摊代价。假设第i次INCREMENT操作对ti个位进行了复位。该操作的实际代价至多为ti+1，因为除了将ti个位复位外，它至多将一位置成1。所以，在第i次操作后计数器中1的个数为bi≦bi-1-ti+1，势差为
平摊代价为
如果计数器开始时为0，则F(D0)=0。因为对所有i有F(Di)≧0，故n次INCREMENT操作的序列的总平摊代价就为总的实际代价的一个上界，且n次INCREMENT操作的最坏情况代价为O(n)。
势能方法给我们提供了一个简易方法来分析开始时不为零的计数器。开始时有b0个1，在n次INCREMENT操作之后有bn个1，此处0≦b0,bn≦k。我们可以将等式（2）重写为：
对所有1≦i≦n有ci≦2。因为F(D0)=b0，F(Dn)=bn，n次INCREMENT操作的总的实际代价为：
请注意因为b0≦k，如果我们执行了至少n=W(k)次INCREMENT操作，则无论计数器中包含什么样的初始值，总的实际代价都是O(n)。
动态表
在有些应用中，在开始的时候无法预知在表中要存储多少个对象。可以先为该表分配一定的空间，但后来可能会觉得不够，这样就要为该表分配一个更大的空间，而表中的对象就复制到新表中。类似地，如果有许多对象被从表中删去了，就应该给原表分配一个更小的空间。在后文中，我们要研究表的动态扩张和收缩的问题。利用平摊分析，我们要证明插入和删除操作的平摊代价为O(1)，即使当它们引起了表的扩张和收缩时具有较大的实际代价也时一样的。此外，我们将看到如何来保证某一动态表中未用的空间始终不超过整个空间的一部分。
假设动态表支持Insert和Delete操作。Insert将某一元素插入表中，该元素占据一个槽（即一个元素占据的空间）。同样地，Delete