17. 摊还分析

在摊还分析中，我们求数据结构的一个操作序列中所执行的所有操作的平均时间，来评价操作的代价。这样，我们就可以说明一个操作的平均代价是很低的，即使序列中某个单一操作的代价很高。摊还分析不同于平均情况分析，它并不涉及概率，它可以保证最坏情况下每个操作的平均性能。

本章介绍三种摊还分析方法：

• 聚合分析
• 核算法
• 势能法

首先我们先看两个小问题

栈操作

对传统的栈操作MULTIPOP(S, k)扩展，伪代码如下，相当于做k次POP(S)

1
2
3
4

MULTIPOP(S, k)
1   while not STACK-EMPTY(S) and k > 0
2       POP(S)
3       k = k - 1

如果在一个包含s个对象的栈上做MULTIPOP(S, k)操作，POP的次数为min(s, k)。

我们来分析一个由n个PUSH/POP/MULTIPOP组成的操作序列在一个空栈上的执行情况。
MULTIPOP的最坏代价为$O(n)$，那么n个操作的最坏代价是$O(n^2)$吗？

二进制计数器递增

k位二进制计数器递增，初始值为0。用一个位数组A[0…k-1]作为计数器。当计数器保存二级制数x时，x的最低位保存在A[0]中，最高位保存在A[k-1]中，因此$x = \sum\limits_{i=0}^{k-1}A[i]\cdot 2^i$。INCREMENT的伪代码如下：

1
2
3
4
5
6
7

INCREMENT(A)
1   i = 0
2   while i < A.length and A[i] == 1
3       A[i] = 0
4       i = i + 1
5   if i < A.length
6       A[i] = 1

可以想象，最坏情况当k位全部是1时，INCREMENT操作要做k次翻转操作，也就是要花费$\Theta(k)$时间，所以对初值为0的计数器，做n次操作的最坏情况花费$O(nk)$次操作？

从上两个问题，我们都根据一个操作最坏情况的时间消耗推测，整个操作序列的时间消耗，显然不是一个确界。下面我们通过三种摊还分析方法来分析这两个问题中每个操作的平均代价（摊还代价）。

聚合分析

聚合分析——确定n个操作最坏情况的总代价$T(n)$，所以每个操作的平均代价为$T(n)/n$。

栈操作：
虽然单独的MULTIPOP操作可能代价很高，但在一个空栈上实行n个操作，POP和MULTIPOP操作的总消耗最多为O(n)，因为只有push进去数据，POP和MULTIPOP才会有消耗，而且PUSH操作每次只能push一个数据进来。所以n个操作最坏情况的总代价为O(n)，除以n得到每个操作的平均代价为O(1)。

二进制计数器递增：
下图展示了二进制计数器从0递增到16的过程，阴影部分表示递增后需要翻转的位。我们可以发现A[0]每次递增时都发生翻转，A[1]每两次递增发生一次翻转，A[2]每四次递增发生一次翻转，以此类推第i位每$2^i$次递增发生一次翻转。也就是说n次INCREMENT操作后，第i位会翻转$\lfloor n/2^i\rfloor$ 次。
执行n次INCREMENT操作产生的总翻转次数为：

$\sum_{i=0}^{k-1}\lfloor n/2^i\rfloor < n\sum_{i=0}^\infty \frac{1}{2^i} = 2n$

所以，n个INCREMENT操作的最坏情况用时为O(n)，除以n得到每个操作的平均代价为O(1)。

核算法

核算法——对不同的操作赋予不同的费用（可以大于或者小于实际的代价，但不能为负值），称其为摊还代价。当一个操作摊还代价大于实际代价时，我们将差额存起来，称其为信用/存款。后续操作如果有摊还代价小于实际代价时，我们将之前存的信用拿出一部分来抵消这里的差值。如果用$c_i$表示第i个操作的实际代价，用$\hat{c}_i$表示第i个操作的摊还代价，则对任意n个操作的序列，要求：

$\sum_{i=1}^n \hat{c}_i \ge \sum_{i=1}^n c_i$

信用总能刚好抵债或者有剩余，从而使得总的摊还代价为总实际代价的上界。

栈操作：
栈操作的实际代价如下：

1
2
3

PUSH       1
POP        1
MULTIPOP   min(k, s)

我们将栈操作的摊还代价设置为：

1
2
3

PUSH       2
POP        0
MULTIPOP   0

每次PUSH操作支付1的实际代价，剩下的1存起来。存起来的钱和堆栈里的数据量相同，而POP或MULTIPOP操作的实际代价为要pop的数据量，所以存款总能保证大于等于零。
每个操作的摊还代价都是常数，所以总的摊还代价为O(n)。

二进制计数器递增：
将INCREMENT中的操作分为置位操作（第6行，0->1）和复位操作（while循环中的操作，1->0）。令置位操作的摊还代价为2，复位操作的摊还代价为0。每次置位操作可以多出1存起来（存起来的钱和计数器中1的个数相同），复位操作需要预支存款，但复位操作只有当某一位是1的时候才会执行，由于计数器中1的个数永远不会为负，所以存款总能保证大于等于零。
每个操作的摊还代价都是常数，所以总的摊还代价为O(n)。

势能法

势能法将数据结构和势能关联起来——对一个初始化数据结构$D_0$执行n个操作。$c_i$为第i个操作的实际代价，$D_i$为第i次操作后的数据结构。势函数$\Phi$将每个数据结构$D_i$映射到一个实数$\Phi(D_i)$，为数据结构$D_i$的势。第i个操作的摊还代价$\hat{c}_i$用势函数$D_0$定义为：

即，每个操作的摊还代价为实际代价加上操作引起的势变化。所以总摊还代价为：

根据公式1可以得到每个步骤的摊还代价，从而算出总的摊还代价，然后根据公式2可以得出总实际代价的上界/下界（$\Phi(D_n) - \Phi(D_{0})$为正数则得到上界，$\Phi(D_n) - \Phi(D_{0})$为负数则得到下界）。

栈操作：
将势函数定义为当前栈中的数据量。
PUSH操作会压入一个数据，所以势差为1，而且实际代价为1，所以PUSH操作的摊还代价为2。
POP/MULTIPOP操作会弹出x个对象，所以势差为-x，而实际代价为x，所以POP/MULTIPOP操作的摊还代价为0。

栈每个操作的摊还代价都是O(1)，所以n个操作的总摊还代价为O(n)。由于初始的栈为空，而结束时栈的数据量大于等于0，也就是说$\Phi(D_n) - \Phi(D_{0})$为正数，所以n个操作的总摊还代价为总实际代价的上界O(n)。

二进制计数器递增：
将势函数定义为计数器中1的个数$b_i$。
假设第i个操作将$t_i$个位复位，则实际代价为$t_i + 1$，因为还有一次置位操作。
再来考虑摊还代价，如果$b_i$为0，则将k位都复位了，因此$b_{i-1} = t_i = k$。
如果$b_i>0$，则$b_i = b_{i-1} - t_i + 1$。无论那种情况都有$b_i \le b_{i-1} - t_i + 1$，所以摊还代价为：

$\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) \le (t_i + 1) + (-t_i + 1) = 2$

所以总摊还代价的上界为O(n)，由于计数器初始状态为0，而1的个数不会为负数，所以n个操作的总摊还代价为总实际代价的上界O(n)。

势能法的还有个优势就是，我们可以简单的得出当初始状态不是0时实际代价的上界。由公式2可得：

$\sum_{i=1}^n c_i \le \sum_{i=1}^n 2 - b_n + b_0 = 2n -b_n + b_0 \le 2n + b_0 \le 2n + k$

所以只要$k=O(n)$那么总实际代价就是O(n)。

动态表

11章介绍了散列表，我们知道散列表的大小和数据量应该是线性相关的，数据太稀疏会浪费空间，数据太稠密会浪费时间。当我们不知道会有多少数据插入时，就没办法确定散列表的大小，所以要引进动态表。
表扩张——当插入数据时发现散列表的装载因子为1（表的大小和数据量相同），对表进行扩张，比如扩张为两倍大小，首先创建一个两倍大小的表，将原来散列表中的数据插入新创建的表中，然后插入新的数据，最后不能忘了把老的表析构。

表收缩——当删除数据时发现散列包的装载因子小于某个值，对表进行收缩，与表的扩张类似，比如收缩为原来表大小的一半，首先删除这个数据并创建一般大小的新表，将原来散列表中的数据插入新创建的表中，然后把老的表析构。

表收缩时判断的装载因子的选择很重要，如果表扩张选择的两倍大小，而表收缩是选择装载因子为二分之一，这时如果在表扩张后立马删除数据，又反复的插入，删除数据，这样会导致表大小的震荡。这种情况下时间机器浪费时间。
所以我们通常可以选择该装载因子为四分之一来避免这个问题。

无论是表扩张还是表收缩，我们都可以用平摊分析来证明动态表的插入和删除操作的平均代价还是O(1)。详细情况参考书中内容，这里不做赘述。