算法导论随笔(十二)：摊还分析(Amortized Analysis)之聚合分析、核算法和势能法

在算法导论随笔(一): 操作计数与复杂度Big（O）中，我简单介绍了计算一个算法的时间复杂度的方法。该方法的计算结果虽然都是正确的，但有时不一定特别准确地代表复杂度函数的渐进上界。因此，人们创建了一个分析方式，可以更精确地表示一个复杂度函数的渐进上界。这个分析方式就是我今天要介绍的摊还分析。

1.为什么要引入摊还分析

前文说到，使用分析操作计数的方法来计算时间复杂度时，有的时候求出的渐进上限并不准确，也就是说，由于我们一直是在考虑程序消耗时间的最坏情况，而程序并不是一直处于最坏情况。因此我们求出的复杂度经常高于真实的复杂度。这里我们举一个简单的例子。假如我们有一个算法，它的代码如下：

int test(int n){int sum = 0;for(int i=0; i<n; i++){if(i % 500 == 0){for(int j=0; j<n; j++){sum += i;}}else{sum++;}}
}

该代码中，存在两个嵌套的循环。其中第5行的for循环只有在i能被500整除的时候才会执行。但是由于我们要考虑最坏情况，因此计算出来的复杂度其实就是O(n²)。但我们心里清楚，其实真实情况远不会消耗O(n²)的时间。而摊还分析，其实就是在分析时考虑了这些情况，因此根据摊还分析计算出的复杂度，就会更低一些，也更精确一些。

2.摊还分析及其分析方式

那么摊还分析是怎样计算复杂度的呢？在《算法导论》第十七章里，对摊还分析是这样描述的：

在摊还分析中，我们求数据结构的一个操作序列中所执行的所有操作的平均时间，来评价操作的代价。这样，我们就可以说明一个操作的平均代价是很低的，即使序列中某个单一操作的代价很高。

也就是说，对于一个数据结构，或者一组数据，例如上面代码中从1到n的遍历，可能其中某一个操作的代价特别高（比如当i能被500整除时，要多运行一个嵌套循环），但其他的操作代价很低。此时，使用摊还分析，可以求出对于该数据结构单个数据操作的平均代价。也就是说，通过对上面的代码进行摊还分析，我们可以求出对于任意一个i∈n，对i的操作代价都是一个相同的平均值，不论i能否被500整除。

在《算法导论》中，介绍了摊还分析的三种方式：聚合分析(Aggregate Analysis)，核算法(Accounting Method)，以及势能法(Potential Method)。接下来我会分别对它们进行讨论。

3. 聚合分析Aggregate Analysis

聚合分析原本自成一派，不过后来被归档入摊还分析之下。《算法导论》里对聚合分析是这样写的：

利用聚合分析，我们证明对所有n，一个n个操作的序列最坏情况下花费的总时间为T(n)。因此，在最坏情况下，每个操作的平均代价，或摊还代价为T(n) / n。

上面的这段话表达的意思就是，对于一个数据结构，或者一组数据，如果我们计算出对它的操作的总时间为T(n)，那么每一个对该数据结构的操作的复杂度都是T(n) / n，不管这个操作的类型是什么。举个例子，假如我们计算出对一个数组的操作总时间为T(n) ，那么对该数组单个数据的操作的复杂度都是T(n) / n，不论这个操作是添加、删除还是修改一个数据。

下面以书上的例子来讲解聚合分析的方法。
假设我们有一个栈，对这个栈有入栈和出栈的操作，也就是PUSH跟POP。
PUSH(S, x)：将对象x压入栈中。
POP(S): 将栈S的栈顶对象弹出，并返回该对象。对空栈调用POP会产生一个错误。

这两个操作的复杂度都为O(1)。因此我们假设它的代价为1。所以对于n个由PUSH和POP组成的操作，其复杂度为O(n)。

现在我们增加一个操作MULTIPOP(S, k)，它弹出栈顶的k个对象。 如果删除前栈S中对象数量少于k个，则弹出全部对象。这里我们规定k应为正整数，若参数k小于等于0，则该函数不做任何事情。来看该操作的伪代码。

在最坏情况下，k=n，因此该操作的复杂度为O(n)。那么问题来了，如果我多次调用MULTIPOP(S, k)函数，所需要的总代价（也就是复杂度）是多少呢？
按以往的计算方式来说，一次MULTIPOP(S, k)的复杂度为O(n)。那么n次MULTIPOP(S, k)的复杂度就是
$$T(n)=n\times O(n)=O(n^2)$$
如果使用聚合分析呢？
我们知道，PUSH和POP的复杂度均为O(1)。而MULTIPOP(S, k)这个操作，其有效操作（即操作之前栈不为空）的次数取决于栈内剩余对象的数量。由于初始状态下栈为空，因此，MULTIPOP所能进行的有效POP次数最多只能等于PUSH的次数，即：之前PUSH了多少次，则最多只能POP多少次。因此，若栈内有n个对象，则n个MULTIPOP的操作，所包含的有效POP次数最多也就是n。

书中是这样说的：

对于任意的n值，任意一个由n个PUSH、POP和MULTIPOP组成的操作序列，最多花费O(n)的时间。

也就是说，计算这n个操作全都是PUSH，栈中也才只有n个对象。因此，不论对栈进行多少次POP，最多也就只有O(n)个有效操作（无效操作不做任何事情，因此也不产生代价）。因此，n个操作的复杂度为O(n)，则每个操作的平均复杂度为
$$T(n)=O(n)/n=O(1)$$
那么n个MULTIPOP的复杂度也就是O(n)，比按之前方法计算出的O(n²)更好，也就是说，我们计算出的上界更紧凑（即更接近其实际运行的代价上界）。

4. 核算法Accounting Method

对于核算法，书中是这样介绍的。

用核算法进行摊还分析时，我们对不同操作赋予不同费用，赋予某些操作的费用可能多于或少于其实际代价。我们将赋予一个操作的费用称为它的摊还代价。当一个操作的摊还代价超出其实际代价时，我们将差额存入数据结构中的特定对象，存入的差额称为信用(credit)。对于后续操作中摊还代价小于实际代价的情况，信用可以用来支付差额。

这段话是什么意思呢？用通俗的语言讲，这个方法类似于买往返票的操作。也就是把一个操作A的代价和该操作未来可能需要的代价都算在这个操作的头上，这样的话，未来对与该操作相关的操作B就不用再计算复杂度了，因为B操作的代价已经由A来支付了。

我们还是用上文所述的栈的例子来说明。对于每一个PUSH、POP和MULTIPOP操作，它们的代价分别如下（min(k, s)表示k值和当前栈内对象数量s之间的最小值）：

而核算法，就是给PUSH操作买了一张往返票。其原因就是，每一个PUSH操作都会把一个对象压入栈中，因此该对象未来就可能会被一个POP操作所弹出。这一压一弹，代价为2。核算法把这2个代价都算在了PUSH头上，而把POP的代价设置为0。而又因为MULTIPOP其实就是多个POP操作，由于POP的代价为0，因此MULTIPOP的代价也是0。因此我们得到核算法赋予每个操作的代价如下图：

因此，意一个由n个PUSH、POP和MULTIPOP组成的操作序列，其代价最高的时候就是所有操作都是PUSH的时候（因为POP和MULTIPOP代价为0），此时代价为n×2=2n，因此n个操作的复杂度为
$$T(n)=O(2n)=O(n)$$
也就是说，就算所有操作都是MULTIPOP，其代价仍为O(n)。

5. 势能法Potential Method

势能法的思想与核算法类似，依旧是类似于买往返票这种提前支付的模式。不同的是，在核算法中，我们是用微观的方式对每一个操作赋予代价；而在势能法中，我们是用宏观的方式来对整个数据结构来进行代价的评估。

这里的势能与物理学有点沾边，比如我们知道的物体的“重力势能”，是随着物体与地面距离增大而增大的。因此，以前文提到的栈这个数据结构为例，我们也可以规定它的势能。该势能初始为0，随着栈内对象数量的增大而增长，随对象数量的减少而减小。

书中把对于一个数据结构的第i个操作的代价定义为如下公式。
c ^ i = c i + ϕ ( D i ) − ϕ ( D i − 1 ) \hat c_i = c_i + \phi(D_i) - \phi(D_{i-1}) c^i​=c