如何理解算法平摊分析中的势能方法（Potential Method）？
算法不是纯数学 要从更“欢脱”的思路来理解，我就是一直这么做的（比如，红黑树是一个想要减肥的胖子） 不要为符号与概念所累 为什么我们需要均摊分析（Amortized Analysis）？ 因为Big O跟病毒一样具有传染性。 大多数时候，需要O的传染性来简化情况，避免陷入到无尽的常数和低阶运算中去，得到更纯粹的解 按算法导论书本的例子 对于一个Stack操作，POP和PUSH都是O(1)的，这很好理解 现在定义了一个新的操作，Multi-POP，表示POP n个元素，显然这是一个O(n)的操作 好了，如果我们进行一连串随机的POP PUSH Multi-POP，那么上界是多少？ 根据O的传染性，O(n) > O(1)，那么单个操作，我们全都按O(n)算，有n个操作，那就是O(n^2)。 有错吗？没有。但直觉告诉你，肯定哪里有什么不对！ 怎么可能存在一个Stack，你可以一直Multi-POP下去？第一次Multi-POP(n)之后，Stack就已经清空了。 这3种操作不是平行的，而是互相影响的。换言之，你每次的PUSH创造“机会”给POP和Multi-POP。POP和Multi-POP才能“消费”着这些机会，不存在无限制的消费。 这是一个被污染的结果，我们需要工具来对抗Big O的传染性。 书中介绍了两种方法 1. Accounting Method 2. Potential Method 两种方法的内核基础是一样的（各个操作是相关的），不同是角度。 Accounting Method，要求你先计算出每个操作要“存”多少钱，然后给别的操作消费。 Stack的每次PUSH都花2元，1元是支付自身的操作，还有1元存起来。 接下来任意的POP和Multi-POP就不用花钱了，因为PUSH操作已经付过了。 这样上界就被我们进一步限制到了O(2n) = O(n) 现在是重头戏，势能方法 这种方法是渐进的，你一开始并不需要知道究竟要存多少钱。 想象一下你正在坐过山车，现在车正在爬坡 等到了最高点，是什么导致了过山车迅速冲下去？物理上管这叫势能。引入到算法之中就是，一些操作，在为回到上一个状态积累势能，一些操作消费这些势能。 再也不用管究竟要存多少钱，要花多少钱了。你只需要证明，每个操作积累的势能是常数的，别的操作只是消费势能就好了，从当一个Accountant的工作中解放出来。 回到Stack的例子 每次的PUSH，Stack的长度都加1，这就好像过山车在爬坡，积累1个势能单位，让其能够在后续的POP和Multi-POP回归到长度为0的状态。 无论Stack有多长，我们都有足够的势能单位，让Stack回归到0。 能理会到跟Accounting Method的差异没？ 如果有看书的童鞋，还可以看到有个计数器的例子，用势能方法也很容易说明。我们先定义，每翻出一个1，那么就是势能状态改变了，需要积累1个势能单位将其变为0的原始值。 每次计数器加1，实际消耗为翻掉1的数量加上1，状态的变化为增加了1个势能单位，但又消费掉了翻掉1的数量的势能单位，对消一下，得到2。这是一个常数操作。 这个例子中的加1操作，既是势能生产者，又是势能消费者。 算法分析条条大路通罗马，即使你不用以上方法，用数列极限一样可以算得出来。