分析给定初始内容递增二进制计数器的复杂性

Question

关键是二进制计数器在开头有一些内容.它是否仍然按时间复杂度摊销？怎么证明呢？

假设我们有11010二进制计数器,我们将它递增,以便它现在11011等等.

单增量运营的摊余成本是多少？

Answer 1

每项业务的摊余成本为O(1).

我们n是在柜台的位数.

In all increment operations, you need to change the LSb
In half of the operations, you need to change the 2nd LSb
In 1/4 of the operations, you need to change the 3rd LSb
...
In 1/(n/2) of the operations, you need to change the (n-1)th LSb (2nd MSb)
In 1/n of the operations, you need to change n'th LSb (MSb).

这为您提供了以下平均表现:

1 + 1/2 + 1/4 + ... + 1/n <=(*) 2

要正式证明它,请使用归纳,修改位数.

(*)来自几何级数的和a=1, r=1/2,当从1到无穷大求和时,得到SUM = 1/(1-r) = 1* 1/(1/2) = 2.由于我们只从这个数字减去,我们实际上得到的总和严格小于2.