【算法导论】摊还分析

在摊还分析中，我们求数据结构的一个操作序列中所执行的所有操作的平均时间，来评价操作的代价。

1.聚合分析

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

下面我们看两个例子。

1.栈操作

我们定义栈操作：

• PUSH(S,x)：将对象x压入栈S中。
• POP(S)：将栈S的栈顶弹出。
• MULTIPOP(S,k)：弹出栈顶的k个对象，不足k个则弹至空栈。

对于一个深度为n的栈，执行n个栈操作，因为任意一个栈操作的最坏情况是 MULTIPOP ，复杂度为O(n)，因此整个栈操作的最坏时间复杂度是O(n^2)。

而我们使用聚合分析，考虑整个序列的n个操作，虽然单个 MULTIPOP 操作的代价很高，但是对于一个空栈上执行n个操作， MULTIPOP 调用的POP次数最多也不过是所有的PUSH次数，也就是整个栈操作的时间复杂度降为了O(n)，同理，对于一个非空栈上执行n次操作，调用的POP次数也不会超过也最多与PUSH操作次数相当，因此最多花费O(n)，因此摊还代价都是O(1)。

2.二进制计数器递增

定义一个二进制计数器有如下操作：

INCREMENT()：二进制计数器+1。

因此该计数器有如下图：

对于该算法，显而易见的不会超过代价的2倍，也就是最坏的时间复杂度不会超过O(2n)。

对于每次 INCREMENT 操作，最后一位都会变化，倒数第二位则每两次变化一次，倒数第三位每4次变化一次以此类推，那么总的操作次数就是2n次。时间复杂度O(n)，摊还代价为O(1)。

2.核算法

我们使用核算法来进行摊还分析时，我们对不同的操作赋予不同的费用，某些费用可能多于或小于其实际代价。我们将这个代价也称为摊还代价。

当一个操作的摊还代价超出其实际代价时，我们将差额存入数据结构的特定对象，存入的差额称为信用（信用值非负）。对于后续操作中摊还代价小于实际代价的情况，信用可以用来支付差额。

1.栈操作

还是刚刚那些栈操作，我们将这些操作赋予如下摊还代价：

• PUSH 2
• POP 0
• MULTIPOP 0

我们将证明，通过摊还代价缴费，我们可以支付任意的栈操作序列。所有的入栈操作均存放了一份出栈代价（一份入栈一份出栈，所以为2），所以无论使用何种出栈方式，代价均可以定义为0。

因此总代价最多为2n，总摊还代价为O(n)，均摊代价为O(1)。

2.二进制计数器递增

对于二进制计数器，我们只要在任何翻转以为二进制的时候，将格外的一份存进去用来将本次翻转翻转回来，也就是每次翻转存入2（一份翻转，一番存做翻转回来的信用），这样对于n次计数，我们代价最高为2n，也就是O(n)，均摊代价为O(1)。

3.势能法

势能法摊还分析并不将预付代价表示为数据结构中特定的信用，而是表示为“势能”，或简称“势”。

我们定义第i个操作的摊还代价为：

因此，总的摊还代价为：

实际上势能法和核算法思想基本一致，就是一个方法的两种角度，核算法是事前诸葛亮——它是在每一次操作前就考虑之后的状态。而势能法是事后诸葛亮——它关心每一次操作后状态的改变。

1.栈操作

举例说明，

对于PUSH操作，假如此时栈中包含s个对象，则势差为：

摊还代价为：

假设第i个操作为MULTIPOP，则对象的代价为k，势差为：

摊还代价为：

同理，POP的摊还代价为0。

因此每个操作的摊还代价依然是O(1)。

4.动态表

类似于Java的HashSet等数据结构，可以进行动态扩张而不必一开始就指定数据的全部长度。

1.表扩张

常用的分配策略是：为新表分配二倍于旧表的空间，如果只允许插入操作，那么装填因子总是保持在1/2以上，因此浪费的龙剑不会超过总空间的一半。

2.表扩张和收缩

为了避免表空间浪费，当装填因子过小的时候，可以对表进行收缩操作。分配一个新的更小的表，然后将数据项从旧表复制到新表之中。