所以情况是这样的，对于 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)，尽管常数更大。
增量函数的聚合分析。 如果我跟进这个细分并在 sigma 内乘以 2^i，因为翻转第 i 位的成本是 2^i，我得到 n 增量的 nk。这仍然给了我 O(1) 的摊销成本
我不确定我在这里做错了什么。直观地说，它仍然是 O(1) 是有意义的，因为高成本的高位只是抵消了它被翻转的低概率。