势能分析法

1. 简述

势能分析是一种非常重要的复杂度分析方法，它和其他的一些分析方法可以认为是本质相同的，尤其是面对一些简单问题的时候我们可能会感觉它们没什么差别。但是当遇到复杂的情形的时候，累加法、借款贷款法就不是那么方便和直观了。它可以帮我们理性分析一些经常被感性理解的复杂度，或者是帮我们证明一些算法即便在某些情况下很耗时但是均摊上依然很优秀。
它的英文 Amortized Analysis 也翻译作摊还分析，这个翻译其实更直观一些。它所做的事情其实就是把消耗大的操作给消耗小的操作匀一点，这就是摊还/平摊。那么到底应该怎么匀？什么情况下匀？我们可以用形式化的语言来简洁明了地描述这件事。

2. 数学语言

现在我们有一种操作，它第步的消耗（这里的消耗是广义的消耗，可以是空间、时间等）我们记为。假设这个操作进行了n步，那么最终的消耗将会是：。现在我们考虑一个势能函数，这里表示的是第步后整个局面的状态。所以我们的势能函数是针对“局面”或者说状态的，和具体的操作没关系只和操作之后的状态有关，这也是它被称为势能函数的原因：势能是保守力对应的能量，它和作用路径无关只和状态有关。
现在我们考虑这样一件事：如果那么我们有。这说明如果我们用这个式子来代替真正的计算次数只会让算出来的数字变得更大，所以用来求上界是非常合适的，前者的上界必然是后者的上界。
而我们显然有：，进而有：。
于是我们得到了势能分析的关键式子：我们把每一步的代价看成是：。

3. 为什么这么做？这么做为什么对？

为什么要这么做呢？这看起来这是一个很无聊的事情，我们给一个和式加了一个正数，显然变大了；然后把这个正数拆成了许多个数的和，分散拆到了和式的每一项里。这整个过程非常的 trivial ，看不出来有什么意义。
想要理解势能的意义，我们只需要一个口诀即可：让消耗大的那一步操作势能大大的降！这个口诀可以帮助我们理解势能的意义。我们把每一步的代码看成了：原本的代价+势能的变化。所以如果原本的代价很大我们让势能大下降，这样就把原本的代价抵消了，也就是所谓的摊还。当然这样做当然不是无止境的，不能每一步都让势能下降，毕竟最终我们要求终点的势能是要大于起点的势能的。所以到时候让代价小的操作的势能上升就可以实现把代价大的操作的代价摊到代价小的操作上了。
那么这样的正确性是很显然的啦，我们不要去想每一步亏了多少赚了多少，我们只需要知道我们最开始的那个式子：最终势能相较于一开始是上升的，所以我们这样做只会让总体的代价变大，对于分析上界不会带来问题。

4. 一些例子

这里我们先举几个简单的例子，它们的复杂度证明往往不用势能分析也可以很简单，这里只是展示一下势能分析的思路。

4.1 二进制进位问题

现在有一个二进制数字，一开始是 0 ，各位数字当然都是 0 。而后每一步我们都让这个数字 + 1，那么有些时候你只需要让最后一位从 0 变成 1 就可以了。但是如果最后一位本身就是 1 的话我们就需要考虑进位的问题，我们会把末尾最长的连续 1 全部变成 0 ，然后再把最后一位变成 1 。可以想见，最差情况我们 + 1 会导致级别的进位次数。所以朴素的分析：数字从 0 变成 n 需要进位次。
那这个放缩实在是太粗糙了，我们考虑势能分析：让消耗大的那一步操作势能大大的降！（这里的消耗就是进位次数）
那么哪个操作的消耗比较大呢？当然是目前各位全是 1 的时候去 + 1 ，这样要进位很多次的。所以我们希望这一步势能大大的降。那么这一步操作会让整个局面发生什么变化呢？很自然的想到进位多就意味着很多之前的 1 变成 0 了；那基于此我们想到怎么设计函数可以让这个变化映射到势能的下降呢？很自然：定义势能函数为当前状态末尾最长的连续 1 的数量就可以了。这样的话当局面里末尾连续 1 很多的时候，进位要发生很多次，但是经过操作之后会有很多 1 变成 0 ，让势能下降，把原本的代价给抵消掉。
写成公式：定义为当前数字末尾连续 1 的数量。那么每一步的均摊代价恒成立。而且显然这个势能函数满足终止状态比初始状态不小于的条件，毕竟一开始根本没有 1 。所以正确性也得到了保证。

4.2 栈 1-Push k-Pop 问题

现在有这样一个栈，它每次可以 Push 进去一个元素，消耗 1 时间；每次可以选择 Pop 任意多元素（只要栈里有），消耗 时间， 为 Pop 的元素个数。现在一共有 个元素，问经过一系列合法操作之后总共消耗多少时间。
这个问题看起来很弱智，因为一个元素最多被加入和弹出一次，所以显然最多是 时间啊。虽然例子很简单，但是的确也是一个不错的势能分析练习题目。我们还是考虑那个口诀：让消耗大的那一步操作势能大大的降！
现在考虑什么操作代价比较大呢？当然是 k-pop 操作啦，它一次就消耗时间。所以我们希望这个操作前后势能可以对应地下降。那么这个操作对局面的改变是什么呢？当然是栈里的元素变少了。所以我们又能很自然的想到势能函数：栈里的元素个数。这样的话 k-pop 虽然耗时，但是也让元素个数对应的变少，进而使得势能下降。

4.3 Splay

势能分析面对这种类型的数据结构会非常有优势，它们往往单次操作最坏复杂度很高，但是均摊复杂度很优秀，一般来说这种数据结构也比较好写。
课件上不加说明的直接给出了势能函数，然后简单分类讨论了一下证明了复杂度的正确性。分类讨论比较无趣冗杂，课件和网络上资料也很多，这里我们主要讨论这个势能函数是怎么想到的。
其实还是那个口诀：让消耗大的那一步操作势能大大的降！
这里什么操作的消耗比较大呢？其实就是这个树是一个很不平衡的树（最夸张的时候就是链），这种时候想要访问一个叶子结点将会调整非常多次。那么我们继续按照套路，考虑这样的操作对局面产生了什么影响，局面发生了什么变化？其实 Splay 的关键思想就在于此，当你需要调整很多次的时候，这些调整会把整个树变得更加“平衡”，这样的话后续的操作就不会遇到这么极端不平衡的情况了。通过感性理解，我们知道了这样的操作会让这个树变得更加平衡，所以我们需要一个量化衡量“平衡”的函数。
其中表示这个点为根的子树的大小。
树越平衡，这个函数的值越小；越不平衡，这个函数的值就越大！为什么如此呢？我们可以如此感性理解，如果这个树很平衡，就意味着一个点的左右子树大小差不多，这使得树上的点分散在了两个子节点上；而一个链则是剩下的点全部集中在一个儿子身上；也可以把这个树理解为决策树，平衡的时候信息量就小，像链一样的时候信息量就大。
P.S. 很多网络上的包括课件上对 Splay 复杂度的证明都没有考虑插入时寻找插入点的位置这件事的代价，实际上这不是一个非常显然的东西，有兴趣的同学可以看这个文章：Splay 的势能分析

5. 总结