algorithm - 如果在索引 k 处翻转一点成本现在是 2^k 而不是 1，那么二进制计数器中的摊销分析会发生什么？

Question

假设翻转位 #i^花费2 i；因此，翻转位#0 花费1，翻转位#1 花费2，翻转位#2 花费4，依此类推。

Increment()如果我们调用n次，调用 的摊销成本是多少？

我认为n增量的成本应该是n ·2 ⁰ /2 ⁰  +  n ·2 ¹ /2 ¹  +  n ·2 ² /2 ²  + … + n ·2 ^{n -1} /2 ^{n -1}  =  n ( n -1) =  O ( n ² )。所以每个增量应该是O ( n )，对吧？但是作业要求我证明它是O (log  n )。我在这里做错了什么？

Answer 1

让我们有 p 位整数并遍历所有2^p可能的值。

0 0 0
0 0 1
0 1 0 
0 1 1
1 0 0 
1 0 1 
1 1 0
1 1 1

最右边的位是翻转2^p次数（在每一步），所以总成本是2^p
第二位是翻转2^(p-1)次数，但成本为 2，所以我们有总成本2^p
..
最重要的位被翻转一次，但有成本2^p，所以我们有整体成本2^p

将所有位的成本相加，我们得到p*2^p所有操作的全部成本。

每次操作（摊销）成本为p*2^p / 2^p = p

但请注意，这是比特数量的成本，我们必须用N术语来表示

N = 2^p 
 so 
p = log(N)

最后，每个操作的摊销复杂度是O(log(N))