algorithm - 需要使用势函数法找到序列的摊销成本

Question

有一个 n 操作序列，如果 i 是 2 的整数次幂，第 i 个操作的成本是 2i，如果 i 是 3 的整数次幂，则第 i 个操作的成本是 3i，所有其他操作的成本是 1。

您好，首先我想说这是一道作业题，我不想让您帮我解决。

我已经用聚合法解决了。为此，我总结了 2 的幂级数和 3 的幂级数，得到的摊销成本为 10。然后我使用会计方法检查了它，对于很长的序列，它没有失败。但我的问题是如何证明它永远不会失败，我可以显示任意长的序列，但它仍然不能保证它在一段时间后不会失败。

我也尝试用势函数法解决它，这是我真正卡住的地方，要设置一个势函数我认为你需要非常有创意，我找不到一些条件表明在这一点上这总是等等，那里也需要一些帮助。

关于如何在会计方法中证明它以及如何设计潜在功能的一些想法就足够了。谢谢

Answer 1

首先，暂时忘掉“1 代表所有其他操作”和“3 的精确幂”位。如果当 i 是 2 的幂时成本只是 2i 会怎么样？

好吧，假设我们假设每个操作花费四次。也就是说，对于每个操作，我们将四枚硬币放入我们的“欠条堆”......然后当我们达到 2 的实际幂时，我们使用这些硬币“支付”。(这是描述潜在函数方法的一种方式。)

第 1 步:存入四个硬币。需要支付 2*1 = 2，所以我们的硬币堆是二。

第 2 步:再存入四枚硬币。需要支付 2*2 = 4，所以我们的堆又是二。

第 3 步:存入四枚硬币。 Pile 现在有六个硬币。

第 4 步:存入四枚硬币。堆现在有十个硬币，但是 4 是 2 的幂，所以是时候支付 4*2 = 8，所以我们的堆又减少到两个硬币。

第 5 步到第 7 步:每人存入四枚硬币。现在总数是 14 个硬币。

第八步:存入4个币(共=18)，花费8*2=16，再次剩下2个币。

很容易证明这里的稳定状态是我们不断将硬币消耗到一个常数 (2)，但我们永远不会低于这个常数。因此，摊销成本为每次操作四个单位。

现在，假设当 i 是 2 的幂(否则为零)时，操作 X 的成本为 2i。假设当 i 是 3 的幂(否则为零)时，操作 Y 的成本为 3i。并假设操作 Z 的成本为 1，除非 i 是 2 的幂或 3 的幂。观察您的问题等同于对每个执行操作 X and Y and Z迭代...因此，如果您可以分别计算出 X、Y 和 Z 的摊销成本，则可以将它们相加以获得总体摊销成本。

我刚刚给了你 X；我把 Y 和 Z 留作练习。 (虽然我不相信最后的答案是10。接近10，也许...)