二进制计数器平摊分析 [英] Binary Counter Amortized Analysis

问题描述

我想你已经知道，如果在阵列中的所有条目从0开始，每一步我们增加了1计数器（通过翻转0和1），然后按摊余成本对于k增量为O（K）。

I guess you already know that if all the entries in the Array starts at 0 and at each step we increment the counter by 1 (by flipping 0's and 1's) then the amortized cost for k increments is O(k).

但是，会发生什么，如果数组以N开头？我虽然也许对于k递增复杂是因为这一事实，即在开始的1的最大数量为日志现在O（的log（n）+ K），（正）。

But, what happens if the Array starts with n ? I though that maybe the complexity for k increments is now O(log(n) + k), because of the fact that in the beginning the maximum number of 1's is log(n).

有什么建议？

在此先感谢

推荐答案

你是对的。有证明这一个以上的方式，其中之一是具有潜在功能。 此链接（和许多其他人）解释的潜在方法。然而，教科书通常要求的电位函数的初始值是0。让我们概括为，它不是这种情况。

You are right. There is more than one way to prove this, one of them is with a potential function. This link (and many others) explain the potential method. However, textbooks usually require that the initial value of the potential function is 0. Let's generalise for the case that it is not.

有关的二进制计数器，计数器的电位的功能是设置为1比特时递增数，则花费K + 1时刻翻转-K 1的0和1 0至1用k的电位降低-1。所以这个增量= ActualTime +（PotentialAfter-PotentialBefore）= k的分期时间+ 1-（K-1）= 2（常量）。

For the binary counter, the potential function of the counter is the number of bits set to 1. When you increment, you spend k+1 time to flip k 1's to 0 and one 0 to 1. The potential decreases by k-1. So the amortised time of this increment = ActualTime+(PotentialAfter-PotentialBefore) = k+1-(k-1) = 2 (constant).

现在看一下部分摊销和实际时间之间的关系，在维基百科的链接。

Now look at the section "Relation between amortized and actual time" in the wikipedia link.

TotalAmortizedTime = TotalActualTime + SumOfChangesToPotential

由于SumOfChangesToPotential是伸缩，它等于FinalPotential-InitialPotential。所以：

Since the SumOfChangesToPotential is telescoping, it is equal to FinalPotential-InitialPotential. So:

TotalAmortizedTime = TotalActualTime + FinalPotential-InitialPotential

其中给出：

TotalActualTime = TotalAmortizedTime - FinalPotential + InitialPotential <= TotalAmortizedTime + InitialPotential

所以，如你所说，总时间对于k递增的顺序开始，n为O（日志N + K）。

So, as you say, the total time for a sequence of k increments starting with n is O(log n + k).

这篇关于二进制计数器平摊分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！