如果在索引 k 处翻转一点成本现在是 2^k 而不是 1，二进制计数器中的摊销分析会发生什么情况？
What happens to amortized analysis in binary counter if flipping a bit at index k costs now 2^k instead of 1?
假设翻转位#i花费2i；因此，翻转位 #0 花费 1，翻转位 #1 花费 2，翻转位 #2 花费 4，依此类推。
如果调用 Increment() 次 n 次，其摊销成本是多少？
我认为 n 增量的成本应该是 n·20/2 0 + n·21/21 + n·22/22 + … +n·2n−1/2n−1 = n(n−1) = O(n2)。所以每个Increment应该是O(n)，对吧？但是作业要求我证明它是 O(log n)。我在这里做错了什么？
让我们有 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))
假设翻转位#i花费2i；因此，翻转位 #0 花费 1，翻转位 #1 花费 2，翻转位 #2 花费 4，依此类推。
如果调用 Increment() 次 n 次，其摊销成本是多少？
我认为 n 增量的成本应该是 n·20/2 0 + n·21/21 + n·22/22 + … +n·2n−1/2n−1 = n(n−1) = O(n2)。所以每个Increment应该是O(n)，对吧？但是作业要求我证明它是 O(log n)。我在这里做错了什么？
让我们有 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))