Algorithm 版 (精华区)

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

会计方法
在平摊分析的会计方法中，我们对不同的操作赋予不同的费值，某些操作的费值比它们
的实际代价或多或少。对每一操作所记的费值即其平摊代价。当一个操作的平摊代价超
过了它的实际代价时，两者的差值就被作为存款赋给数据结构中一些特定的对象。存款
可在以后用于补偿那些其平摊代价低于其实际代价的操作。这样，我们就可将一操作的
平摊代价看作为两部分——实际代价与存款(或被储蓄或被使用)。这与聚集方法有很大
不同，后者所有操作都具有相同的平摊代价。
在选择操作的平摊代价时是要非常小心的。如果我们希望通过对平摊代价的分析说明每
次操作具有较小的最坏情况平均代价，则操作序列的总的平摊代价就必须是该序列的总
的实际代价的一个上界。而且，像在聚集方法中一样，这种关系必须对所有的操作序列
都成立。这样，与该数据结构相联系的存款始终应该是非负的，因为它表示了总的平摊
代价超过总的实际代价的部分。如果允许总的存款为负的话(开始时对某些操作的费值记
得过低)，则在某一时刻总的平摊代价就会低于总的实际代价。对到该时刻为止的操作序
列来说，总的平摊代价就不会是总的实际代价的一个上界。所以，我们必须始终注意数
据结构中的总存款不能是负的。
栈操作
为了说明平摊分析中的会计方法，我们再回过头看看栈的例子。各栈操作的实际代价为
：
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元余款，并用它来支付弹出操作的实际代价。这样，在对P
USH操作多收了一点费后，就无需对POP操作收取任何费用。
更进一步，我们对MULTIPOP操作也无需收费。为弹出第一个盘子，我们取出其中的1元余
款并用它支付一次POP操作的实际代价。为弹出第二个盘子，再取出该盘子上的1元余款
来支付第二次POP操作，等等。这样，对任意的包含n次PUSH，POP和MULTIPOP操作的序列
，总的平摊代价就是其总的实际代价的一个上界。又因为总的平摊代价为O(n)，故总的
实际代价也为O(n)。
二进制计数器的增值
为进一步说明会计方法，我们再来分析一下作用于一个初始为0的二进制计数器上的INC
REMENT操作。我们前面已经说过，这个操作的运行时间与发生翻转的位数是成正比的，
而位数在本例中即为代价。我们还是用1元钱来表示位数代价(此例中即为某一位的翻转
)。
为进行平摊分析，我们规定对将某一位置为1的操作收取2元的平摊费用。当某数位被设
定后，我们用2元中的1元来支付置位操作的实际代价，而将另1元存在该位上作为余款。
在任何时间点上，计数器中每个1上都有1元余款。这样在将某位复位成0时不用支付任何
费用，只要取出该位上的1元余款即可。
现在就可以来确定INCREMENT的平摊代价了。在while循环中复位操作的代价是由有关位
上的余款来支付的。在INCREMENT的第6行中至多有一位被复位，所以一次INCREMENT操作
的代价至多为2元。又因为计数器中为1的位数始终是非负的，故其中总的余款额也是非
负的。对n次INCREMENT操作，总的平摊代价为2n元，即O(n)，这就给出了总的实际代价
的一个界。

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

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