如果现在将索引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 花费2 ⁱ ；因此，翻转比特0的成本为1，翻转比特1的成本为2，翻转比特2的成本为4，依此类推。

Suppose that flipping bit #i costs 2ⁱ; so, flipping bit #0 costs 1, flipping bit #1 costs 2, flipping bit #2 costs 4, and so on.

通话的摊销成本是多少到 Increment（），如果我们称之为 n 次？

What is the amortized cost of a call to Increment(), if we call it n times?

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

I think the cost for n Increments should be n·2⁰/2⁰ + n·2¹/2¹ + n·2²/2² + … +n·2ⁿ⁻¹/2ⁿ⁻¹ = n(n−1) = O(n²). So each Increment should be O(n), right? But the assignment requires me to prove that it's O(log n). What have I done wrong here?

推荐答案

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

Let we have p-bit integer and walk through all 2^p possible values.

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

The rightmost bit is flipped 2^p times (at every step), so overall cost is 2^p
The second bit is flipped 2^(p-1) times but with cost 2, so we have overall cost 2^p
..
The most significant bit is flipped once, but with cost 2^p, so we have overall cost 2^p

所有位的总和，我们对所有操作都拥有全部成本 p * 2 ^ p 。

Summing costs for all bits, we have full cost p*2^p for all operations.

每次操作（摊销）费用为 p * 2 ^ p / 2 ^ p = p

Per-operation (amortized) cost is p*2^p / 2^p = p

但请注意这是位数成本，我们必须用 N 项来表达

But note this is cost in bit quantity, and we must express it in N terms

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

每个操作的最终摊销复杂度为 O（ log（N））

Finally amortized complexity per operation is O(log(N))

这篇关于如果现在将索引k的位翻转为2 ^ k而不是1，那么二进制计数器中的摊销分析会怎样？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！