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

Question

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

但是，如果数组以 n 开头会怎样？我虽然 k 增量的复杂度现在可能是 O(log(n) + k)，因为在开始时 1 的最大数量是 log(n)。

有什么建议吗？

提前致谢

Answer 1

你是对的。证明这一点的方法不止一种，其中一种是具有潜在功能。 This link (和许多其他人)解释潜在的方法。然而，教科书上通常要求势函数的初值为0，我们就归纳为不是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)。