algorithm - 幂3计数器的摊销分析

Question

我经常阅读算法教科书 Cormen、Liserson、Rivest 和 Stein。

其中一个有趣的章节是摊销分析。在选择势函数时，二进制计数器是一个困难的例子。我想知道如果计数器是 3 的幂和一些系数（例如 x1*1 + x2*3 + x3*9 +...），该怎么办。

在这种情况下如何确定势函数？

标签： algorithmamortized-analysis

Answer 1

为了证明增加一个以 3 为底的计数器需要恒定的摊销时间，可以使用势法，将当前值中 2 的个数作为势函数。

一个增量操作可以分为两部分：

1. 值末尾的连续 2 变为 0。

2. 这些 2 左侧的第一个数字递增。

步骤 (1) 所做的功与从状态中移除的 2s 的数量成正比。

这些 2 中的每一个都是由先前操作的 Step(2) 添加的，这需要恒定的时间并且最多添加一个 2。

设 Φ 为当前状态下 2 的数量。

• 步骤 (1) 花费的时间与它减少 Φ 的量成正比。由于 Φ 始终 >= 0，因此在步骤（1）中在许多增量上完成的总功最多与 Φ 增加的总量成正比。
• 在每个增量中，步骤 (2) 花费恒定时间并增加 Φ - 步骤 (1) 最终可以执行的总工作 - 最多 1，表示实际执行的工作量恒定，并且恒定为步骤 (1) 排队的工作量。这就是在当前和未来增量中摊销的恒定工作量。