我经常阅读算法教科书 Cormen、Liserson、Rivest 和 Stein。
其中一个有趣的章节是摊销分析。在选择势函数时,二进制计数器是一个困难的例子。我想知道如果计数器是 3 的幂和一些系数(例如 x1*1 + x2*3 + x3*9 +...),该怎么办。
在这种情况下如何确定势函数?
我经常阅读算法教科书 Cormen、Liserson、Rivest 和 Stein。
其中一个有趣的章节是摊销分析。在选择势函数时,二进制计数器是一个困难的例子。我想知道如果计数器是 3 的幂和一些系数(例如 x1*1 + x2*3 + x3*9 +...),该怎么办。
在这种情况下如何确定势函数?
为了证明增加一个以 3 为底的计数器需要恒定的摊销时间,可以使用势法,将当前值中 2 的个数作为势函数。
一个增量操作可以分为两部分:
值末尾的连续 2 变为 0。
这些 2 左侧的第一个数字递增。
步骤 (1) 所做的功与从状态中移除的 2s 的数量成正比。
这些 2 中的每一个都是由先前操作的 Step(2) 添加的,这需要恒定的时间并且最多添加一个 2。
设 Φ 为当前状态下 2 的数量。