algorithm - 二进制计数器摊销分析

Question

我猜你已经知道，如果数组中的所有条目都从 0 开始，并且在每一步我们将计数器增加 1（通过翻转 0 和 1），那么 k 增量的摊销成本为 O(k)。

但是，如果数组以 n 开头会发生什么？我认为 k 增量的复杂性现在可能是 O(log(n) + k)，因为在开始时 1 的最大数量是 log(n)。

有什么建议么 ？

提前致谢

Answer 1

你说的对。有不止一种方法可以证明这一点，其中之一是具有势函数。此链接（和许多其他链接）解释了潜在的方法。但是，教科书通常要求势函数的初始值为0。我们针对不是的情况进行概括。

对于二进制计数器，计数器的势函数是设置为 1 的位数。当您递增时，您花费 k+1 时间将 k 个 1 翻转为 0，将一个 0 翻转为 1。势能减少 k-1。所以这个增量的摊销时间 = ActualTime+(PotentialAfter-PotentialBefore) = k+1-(k-1) = 2（常数）。

现在查看维基百科链接中的“摊销时间与实际时间之间的关系”部分。

TotalAmortizedTime = TotalActualTime + SumOfChangesToPotential

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

TotalAmortizedTime = TotalActualTime + FinalPotential-InitialPotential

这使：

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

因此，正如您所说，从 n 开始的 k 个增量序列的总时间为 O(log n + k)。