【算法】平摊分析

0.引子

执行一系列数据结构上操作的时间复杂度，可以通过对每个操作的时间复杂度进行分析，取平均，进行估计。

常用的方法有三种：聚焦方法、会计方法、势能方法。

1.聚焦方法

该方法大意为：考察每个操作的最坏时间复杂度，然后作平均得到整体的一个复杂度上界。

这个方法比较简单，易于操作，但是它估计出来的结果有的时候非常不精确，放缩的范围太大。

实例：栈操作

考察：初始栈为空，经过一系列操作的代价。操作有三种：

• Push：压栈。
• Pop：弹栈。
• MultiPop：多重弹栈。

由于一个对象在每次压栈后，至多被弹出一次，MultiPop弹栈的次数折算成Pop的次数，必然和压栈次数相等。如果压栈n次，那么MultiPop折算成Pop，也相当于Pop了n次，设最终栈空，则整体代价为2n=O(n)，平摊下来，每个操作都是O(1)的复杂度。

2.会计方法

一系列操作的实际代价可能彼此不同。那么我们可以为每种操作分配不同的平摊代价，其有两种情况：

• 如果平摊代价大于、等于实际代价，则平摊代价一部分用于抵消实际代价，一部分用于当作余额，支付其他操作的代价。
• 如果平摊代价小于实际代价，则平摊代价全部用作抵消自身实际代价，还要从其他操作的余额中索取一部分，补充抵消自身的代价。

我们选取的平摊代价之和，必须大于实际代价之和，这样我们才能获取一个整体的代价上界，来估计实际代价。

实例：栈操作

已知三种状态的实际代价为：

• Cost(Push)=1
• Cost(Pop)=1
• Cost(MultiPop)=min(n,k)，k为栈中元素个数，n为MultiPop折算成Pop的弹栈次数。

平摊代价为：

• Cost(Push)=2,一个1用来支付Push的开销，剩下一个1用来预支Pop的开销。
• Cost(Pop)=0。
• Cost(MultiPop)=0。

那么最坏总代价（最终栈空）为2n,n为压栈次数。总平摊代价也就为O(n)，每个操作的平摊代价就是O(1)。

3.势能方法

我们把进行一个操作的前后看作两个状态的转变，设每个状态$D_i$都有一个势能（潜力）$\phi(D_i)$，那么代价就是：
$$
AmortizedCost(Procedure)=ActualCost(Procedure)+\Delta\phi
$$
势能怎么得到？认为规定即可，但是它要满足几个条件：

• 恒正。
• $\phi(D_i)\ge\phi(D_0)$，保证总平摊代价是总实际代价的上界。

实例：栈操作

规定$\phi(D_i)$为$D_i$状态下，栈中元素的个数，那么对于每个操作来说，它们的平摊代价为：

• Cost(Push)=1+n-(n-1)=2
• Cost(Pop)=1+(n-1)-n=0
• Cost(MultiPop)=0

n个栈操作的最坏总平摊代价为2n，其他结论同上。