Algorithm 版 (精华区)

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

势能方法
平摊分析中的势能方法不是将已预付的工作作为存储在数据结构特定对象中的存款来表
示，而是表示成--种“势能”，或“势”，它在需要时可释放出来以支付后面操作的代
价。势是与整个数据结构而不是其中的个别对象发生联系的。
势能方法的工作过程是这样：开始时先对一个初始数据结构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)。

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

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