修正增量函数的摊余成本

因此，对于 n 位二进制字符串 A[0....n-1]，其中 A[0] 是最低有效位，A[n-1] 是最高有效位，增量算法为：

Increment(A,n):
i←0
while i<k and A[i]=1 do
   A[i] ← 0
   i ← i+1
if i < k then
   A[i] ← 1

但是在索引 k 处翻转一点的成本是 2^k

我无法证明这种修改后的二进制增量算法的摊余成本是 O(logn)。无论我如何尝试处理，摊余成本似乎仍然很大 O(1)，尽管常数更大。

增量函数的聚合分析。 https://i.stack.imgur.com/BLXiX.jpg如果我跟进这个细分并在 sigma 内乘以 2^i，因为翻转第 i 位的成本是 2^i，我得到 nk 的 n 增量。这仍然给我 O(1) 的摊余成本

我不确定我在这里做错了什么。直观上，它仍然是 O(1) 是有意义的，因为高成本的高位恰好抵消了它被翻转的低概率。

如果我们将计数器从 0 增加到 2^m，则每位翻转多少次？

Bit 0 flips 2^m times. Bit 1 flips 2^m-1 times. But 2 flips 2^m-2 times, etc...

如果我们计算总成本：

Bit 0 costs 1 * 2^m. Bit 1 costs 2*2^m = 2^m. Bit 2 costs 4*2^m-2 = 2^m, etc...

Every bit that changes has the same total cost, and there are m+1 bits that change, so the total cost (m+1)2^m

If number of increments n = 2^m then the amortized cost per increment is

(m+1)2^m/n

= ((log₂n)+1)*n/n

= 1+log₂n