algorithm - 如何在摊销分析中提出潜在功能？

Question

我已经阅读了一些关于摊销分析的帖子，但我在理解潜在方法方面仍然存在一些问题。

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

例如，有一个问题：

对数据结构执行一系列 n 操作。如果 i 是 2 的精确幂，则第 i 个操作的成本为 i，否则为 1。使用潜在方法来确定每次操作的摊销成本。

采用势函数，首先要提出一个势函数： . 有人告诉我，这很直观，但即使经过几个小时我也无法想出这个......

我发现有一个类似的问题：

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

但是，我认为答案是关于帐户方法的。

Answer 1

暗示：

k每次增加（显然），该术语都会k增加，并且增加1.

项2^ceiling(Lg(k))每增加一次，k达到 的新幂2，并且增加i/2。