如何在摊销分析中提出潜在函数？

Question

我已经阅读了一些关于摊销分析的帖子，但在理解潜力法（potential method）方面仍有一些疑问。

主要问题在于如何开发一种正式的潜力函数？以及如何评估潜力函数的正确性？

例如，有一个问题：

对数据结构执行n个操作的序列。如果i是2的幂，则第i个操作的成本为i，否则为1。使用潜力法确定每个操作的平摊代价。

采用潜力函数，我们首先应该提出一个潜力函数：Φ = 2 * (number of expensive operations) - (total number of operations)。有人告诉我这很直观，但即使经过几个小时的思考，我也想不到这个答案...

我发现有一个类似的问题：需要使用潜力函数方法找到序列的平摊成本。然而，我认为答案是关于记账法（account method）的。

- chain ro

Answer 1

提示：

当 k 增加时（显然），术语 k 也会增加，并且它增加了 1。

当 k 到达一个新的 2 的幂时，术语 2^ceiling(Lg(k)) 也会增加，它增加了 i/2。

- user1196549

---

谢谢。现在我理解的是，每当 k 是 2 的幂时，它必须支付 k 单位的费用。 因此，我们可以将这些 k 摊销到以前的 k/2 单位中。通过这种方式，我们开发出了一个具有常数 2 的势能函数。 - chain ro

是的，你明白了。每次支付1元和额外的摊销1元（即平均而言）。 - user1196549