浅谈势能分析法

wqtt · 2025-01-19 10:28:31 · 算法·理论

引入

势能分析是一种非常重要的复杂度分析方法，它和其他的一些分析方法可以认为是本质相同的，尤其是面对一些简单问题的时候我们可能会感觉它们没什么差别。但是当遇到复杂的情形的时候，其他的方法就不是那么方便和直观了。

它是均摊复杂度的分析方法之一，可以帮我们理性分析一些经常被感性理解的复杂度，或者是帮我们证明一些算法即便在某些情况下很耗时但是均摊上依然很优秀。

它的英文 Amortized Analysis 也翻译作摊还分析，这个翻译其实更直观一些。它所做的事情其实就是把消耗大的操作给消耗小的操作匀一点，这就是摊还/平摊。

数学语言

现在我们有一种操作，它第 i 步的消耗（这里的消耗是广义的消耗，可以是空间、时间等）我们记为 c_i。假设这个操作进行了 n 步，那么最终的消耗将会是：\sum_{i=1}^n c_i。现在我们考虑一个势能函数 \phi{S} ，S_i 表示第 i 步后整个局面的状态。

因此我们的势能函数是针对“局面”或者“状态”说的，和具体的操作没关系只和操作之后的状态有关，这也是它被称为势能函数的原因：势能是保守力对应的能量，它和作用路径无关只和状态有关。

第 i 个操作的摊还代价 \hat{c}_i 用势函数 \phi 定义为：

\hat{c}_i=c_i+\phi{S_i}−\phi{S_{i−1}}

于是，n 个操作的总摊还代价为

\sum_{i=1}^n\hat{c}_i=\sum_{i=1}^nc_i+\phi{S_i}−\phi{S_{i−1}}=\sum_{i=1}^nc_i+\phi{S_{n}}-\phi{S_0}

此时，如果能定义一个势函数 \phi ，使得 \phi{S_i}\ge \phi{S_0}，那么显然此时总摊还代价就是总实际代价的一个上界。

所以在定义势能函数的时候要满足要求：

总摊还复杂度不会超出期望复杂度太多（视时间需要而定）；
时间消耗大的步骤消耗势能，时间消耗小的步骤积累势能。（原因下一个会讲）

为什么这么做？这么做为什么对？

为什么要这么做呢？这看起来这是一个很无聊的事情，我们给一个和式加了一个正数，显然变大了；然后把这个正数拆成了许多个数的和，分散拆到了和式的每一项里。这整个过程非常的 trivial ，看不出来有什么意义。

其实想要理解势能的意义，我们只需要一个口诀即可：让消耗大的操作的势能大大的降！

我们把均摊复杂度看成了：原本的复杂度+势能的变化。所以如果原本的代价很大我们让势能大大下降，这样就把原本的代价抵消了，也就是所谓的摊还。当然，这样不是无止境的，不能每一步势能都下降，毕竟最终我们要求终点的势能是要大于起点的势能的。所以到时候让代价小的操作的势能上升就可以实现把代价大的操作摊的代价到代价小的操作上了。

正确性是显然的，我们不要去想每一步亏了多少赚了多少，我们只需要知道我们最开始的那个式子：最终势能相较于一开始是上升的。所以我们这样做只会让总体的代价变大，对于分析上界不会带来问题。

一些例子

建议在看完问题之后先自己想一下，想不出来再看解析。

1. 栈问题

现有一个栈，有 pop、push 和 multipop 三种操作，分别是弹出栈顶，压入栈，批量弹出。压入、弹出单个元素的单次时间复杂度为 \mathcal{O}(1)。求 n 次操作的平摊复杂度，保证每次操作都合法。

口诀：让消耗大的操作的势能大大的降。 这里操作最大的无非批量出栈，这启发我们设 \phi(S)= 栈中的元素个数。显然满足上述几个要求。

那么对于 pop 操作，\hat{c}_i=1+\phi{S_i}-\phi{S_{i-1}}=0；

对于 push 操作，\hat{c}_i=1+\phi{S_i}-\phi{S_{i-1}}=2；

对于 multipop，我们设 n 为他原本的元素个数，k 为他弹出的元素个数，则 \hat{c}_i=1+\phi{S_i}-\phi{S_{i-1}}=k+(n-k)-n=0。

所以均摊复杂度就是 \mathcal{O}(1)。不过也可以从每个元素至多入栈和出栈各一次的角度来分析。

2. 动态数组倍增问题

给定一个数组，其初始大小为 0，支持在数组末尾加入一个元素；如果当前大小为 0，则先开 1 的空间，如果数组元素已满，则先将数组的大小翻倍再插入，插入一个元素的时间视为 1，开空间的复杂度可忽略不计。求操作的平摊复杂度。

我们发现，消耗最大的操作无疑是将数组翻倍再插入的操作，我们肯定想让这个操作之后的状态尽可能小。由此想到，数组剩余空间越多的势能越小。所以可以设 \phi{S}=-(m-n)，m 表示此时数组的大小，n 表示此时数组中的元素个数。但是这个时候，\phi 可能会是负数呀。所以我们再改一下 \phi{S}=2n-m。n 始终大于 \frac{m}{2}，所以 \forall i,\phi{S_i}\ge 0，并且也满足其他几项要求。

那么对于加入一个元素，\hat{c}_i=1+\phi{S_i}-\phi{S_{i-1}}=1+2(n+1)-m-(2n-m)=3

对于开一倍空间、复制一遍再加入，\hat{c}_i=n+1+\phi{S_i}-\phi{S_{i-1}}=n+1+2(n+1)-2n-(2n-n)=3

均摊复杂度为 \mathcal{O}(1)。

3. 二进制进位问题

现在有一个二进制数，一开始是 0。而后每一步我们都让这个数字 +1。有些时候你只需要让最后一位从 0 变成 1 就可以了，但是如果最后一位本身就是 1 ，我们就会把末尾最长的连续 1 全部变成 0 ，然后再把最后一位变成 1。假设更改一个数位的复杂度为 1，试证明 n 次操作的均摊复杂度是 \mathcal{O}(1)。

还是围绕着那个口诀来。这个操作次数大的时候肯定是末尾有一长串连续的 1 的时候，而操作完之后末尾就会留下一长串的 0。因此，我们设 \phi{S}= 二进制数中 1 的个数。显然满足要求。

设 n 表示其中 1 的个数，k 表示末尾连续的 1 的数量。

对于末尾本身就是 0，\hat{c}_i=1+\phi{S_i}-\phi{S_{i-1}}=1+n+1-n=2；

对于末尾存在 1 的，\hat{c}_i=k+1+\phi{S_i}-\phi{S_{i-1}}=k+1+n-k+1-n=2。

因此，均摊复杂度就是 \mathcal{O}(1)。

4. Splay 复杂度分析

势能分析面对这种类型的数据结构会非常有优势，它们往往单次操作最坏复杂度很高，但是均摊复杂度很优秀，一般来说这种数据结构也比较好写。

Splay 的具体代数证明，网上有很多，在此我就不过多阐述（~~懒得写~~）。我主要讨论这个势能函数是怎么想到的。

其实还是那个口诀：让消耗大的操作的势能大大的降！ 消耗比较大的操作，显然是 Splay 极不平衡的时候（最夸张的就是链）。这种时候想要访问一个叶子结点将会调整非常多次。那么我们继续按照套路，考虑这样的操作对局面产生了什么影响？其实 Splay 的关键思想就在于此，当你需要调整很多次的时候，这些调整会把整个树变得更加“平衡”，这样的话后续的操作就不会遇到这么极端不平衡的情况了。

通过感性理解，我们知道了这样的操作会让这个树变得更加平衡，所以我们需要一个量化衡量“平衡”的函数。 因此，就有：

\phi{S}=\sum_{i=1}^n\log{siz_i}

树越平衡，这个函数的值越小；越不平衡，这个函数的值就越大！ 为什么如此呢？我们还是可以感性理解，如果这个树很平衡，就意味着一个点的左右子树大小差不多，这使得树上的点分散在了两个子节点上；而一个链则是剩下的点全部集中在一个儿子身上；也可以把这个树理解为决策树，平衡的时候信息量就小，像链一样的时候信息量就大。 (有人会问为什么不是 \sum_{i=1}^n siz_i，因为这样就与我们的期望时间复杂度相去甚远)。

参考资料

时间复杂度-势能分析浅谈 - 洛谷专栏

算法 - 势能分析法 - 《算法 · 运筹 · 组合优化》 - 极客文档

势能分析法 - Dfkuaid - 博客园

OI-wiki 势能分析