关于二进制计数器摊销分析 [英] Regarding binary counter amortized analysis
问题描述
这是关于二进制计数器的平摊分析。在阵列中的所有条目从0开始，每一步，我们将简单地增加计数器。
This is regarding amortized analysis of binary counter. All the entries in the Array start at 0 and at each step we will be simply incrementing the counter.
下面笔者提如下。
我们使用的是潜在的功能，它等于1比特的当前计数的数目
We are using a potential function that is equal to the number of 1-bits in the current count.
问题1：上面的语句是什么意思
Question 1: What does above statement mean?
和其他问题我已经是在它被提及为
And other question i have is in the analysis it is mentioned as
的n +（N / 2）+（N / 4）+ ...是atmost 2n个。我们是如何走到导致的atmost 2N？
n+(n/2)+(n/4)+--- is atmost 2n. how we got result as atmost 2n?
谢谢！
推荐答案
有递增这个例子中的成本的比特翻转到执行数
The costs for incrementing in this example are the number of bit-flips to execute.
即。递增3（ 0b11 ）至4（<$ C C $> 0b100时）有3成本（全部三个位置翻转）。
I.e. incrementing 3 (0b11) to 4 (0b100) has cost of 3 (all three positions flipped).
现在与你不能说，该算法是分期常量，因为时间的量取决于位翻转数量，从而改变上号。
Now with that you couldn't say, that the algorithm is amortized constant, because the amount of time depends on the number of bit-flips and thus varies on the number.
要解决一个使用的潜在方法上的增量操作的从0开始的潜在的序列是现在的1个位的数量。
To work around that one use the potential method on a sequence of increment operations starting with 0. The potential is now the number of bits that are 1.
- 在φ（0）= 0
- 在φ（1）= 1
- 在φ（2）= 1
- 在φ（3）= 2
- 在φ（4）= 1等
这是有意义的，因为对于每个比特是1，在未来的增量操作将必须把它更改为0在一些点。所以每当在增量发生，需要翻转以上的最后一个比特，它利用价值的潜在的
This makes sense, since for each bit that is 1, an increment operation in the future will have to change it to 0 at some point. So whenever in increment occurs that needs to flip more than the last bit, it makes use of the potential of the value.
现在继续平摊分析，你会发现，那潜在的总是1和你降低你翻转每1位的潜力每个增量操作会增加。在每个操作结合这一点，你有2费用：节约1的潜力）翻转0到1，B）。翻转所有的人之前，0 支付的使用潜力。
Now continuing the amortized analysis, you will find, that the potential always increases by 1 and in each increment operation you decrease the potential for every 1 bit you flipped. Combining this in each operation you have costs of 2: a) flipping a 0 to a 1, b) saving 1 for the potential. Flipping all the ones before the 0 is paid using the potential.
另请参阅： http://en.wikipedia.org/wiki/Potential_method
这篇关于关于二进制计数器摊销分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
