一文掌握算法思想，一个二进制计数器教会我们平摊分析……

正文

请到「今天看啥」查看全文

可以观察到，并不是每次加1操作所有二进制位都会翻转。 聚集分析法，就是要确定n个操作序列的总代价的上界T(n)，也就是最坏情况下为T(n)，每个操作的平均代价为T(n)/n，这个平均代价也叫做平摊代价，即不管每个不同操作的实际代价是什么，它们都有相同的平摊代价。 下面来求T(n)。

A[0]每次都要翻转，翻转n次；

A[1]每隔一次翻转，翻转n/2次；

A[2]每隔三次翻转，翻转n/4次；

A[3]每隔七次翻转，翻转n/8次；

...

那么二进制计数器累计加1直到n总共要做的翻转次数为

于是通过聚集分析方法可以得到，最坏情况下计数器A由0计数到n的操作时间T(n)=2n，每次操作的平摊代价为T(n)/n=O(1)，作用于一个初始为0的二进制计数器上的n次加1操作的时间复杂度至多为O(n)。

2.2记账分析法

以上是用聚集分析方法来分析二进制计数器加1操作的复杂度。 平摊分析还有另外一种常用的方法，叫做记账方法。 在聚集分析法中，每次加1操作的平摊代价由总的代价平均而来，每次加1操作都有相同的平摊代价。 但是在记账方法中，要给每一次加1操作分别定义平摊代价，现做如下定义：

由0翻转为1的实际代价为1；

由1翻转为0的实际代价为1；

由0翻转为1的平摊代价为2；

由1翻转为0的平摊代价为0；

由0翻转为1的平摊代价定义为 2，其中1用来支付翻转的实际代价，1用来作为该位上的“存款”，也就是说每出现一次由0翻转为1的操作，那么该二进制位上就会有1的“存款”，当该二进制位由1翻转为0时，就可以用这现有的“存款”1，去支付由1翻转为0的实际代价，因此由1翻转为0的平摊代价也相应定义为0。

基于以上定义，可以得到如下结论：

（1）对二进制计数器的每次加1操作，其平摊代价为2

二进制计数器加1操作通常由如下算法实现

Increment(A)

{

i=0

While(i

{A[i]=0;i=i+1}

if (i

{A[i]=1}

}

也就是说从二进制计数器最低位开始，依次向高位查找，遇到1就将其翻转为0 ，直到遇到第一个0，将其翻转为1。 在该过程中只会出现一次将0翻转为1，因此计数器A加1操作的平摊代价始终是2。

请到「今天看啥」查看全文