Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 聚集方法
发信站: 哈工大紫丁香 (2002年03月22日14:48:42 星期五), 站内信件

聚集方法
在平摊分析的聚集方法中，我们要证明对所有的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≠0
2    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个PU
SH，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←0
2  while i<length[A] and A[i]=1
3    do A[i]←0
4       i←i+1
5  if i<length[A]
6    then A[i]←1
这个算法与硬件实现的行波进位计数器基本上是一样的。图2演示了一个二进制计数器从
0至16的16次增值的过程。发生翻转而取得下一个值的位都加了阴影。右边示出了位翻转
所需的代价。注意总代价始终不超过INCREMENT操作总次数的两倍。在第2-4行中每次wh
ile循环的开始，我们希望在位置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
Value A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0] Total
Cost
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

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]