修正增量函数的摊销成本 [英] amortized cost of modified increment function

问题描述

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

So the scenario goes, the increment algorithm, for n bit binary string A[0....n-1], where A[0] is the least significant bit and A[n-1] is the most significant bit, is:

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）大。

I'm lost on trying to prove that the amortized cost of this modified binary increment algorithm is O(logn). No matter how I try to approach, it still seems like the amortized cost would be big O(1), though with a bigger constant.

对增量函数进行汇总分析。
，如果我继续进行此细分并在sigma中乘以2 ^ i，因为翻转第i位的成本为2 ^ i，则得到n个增量的nk。这仍然给了我O（1）的摊销成本。

aggregated analysis of the increment function. if I follow up on this breakdown and multiply by 2^i inside the sigma, since for the cost of flipping the ith bit is 2^i, I get nk for n increments. Which still gives me amortized cost of O(1)

我不确定我在这里做错了什么。从直觉上讲，它仍然为O（1）是有意义的，因为高成本的高位只是抵消了它被翻转的低概率。

I am not sure what I'm doing wrong here. Intuitively it makes sense for it to be still O(1) since the high cost higher bits just cancels out the low probability of it being flipped.

推荐答案

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

If we increment the counter from 0 up to 2^m, how many times does each bit flip?

位0翻转2 ^m 次。位1翻转2 ^m-1 次。但是2次翻转2 ^m-2 次，等等...

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

如果我们计算总成本：

位0花费1 * 2 ^m 。位1的费用为2 * 2 ^m = 2 ^m 。位2花费4 * 2 ^m-2 = 2 ^m ，依此类推...

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

每个变化的位具有相同的总成本，并且有m + 1个位发生变化，因此总成本（m + 1）2 ^m

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

如果增量数n = 2 ^m ，则每次增量的摊销成本为

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

（m + 1）2 ^m / n

(m+1)2^m/n

=（（log ₂ n）+1）* n / n

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

= 1 + log ₂ n

= 1+log₂n

这篇关于修正增量函数的摊销成本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！