跳转至

摊还分析

重点
  • 平摊分析方法的作用和三种平摊分析方法各自特点；
  • 聚集分析法及应用；
  • 记账分析法及应用；
  • 势能法及应用。

基本思想

摊还分析的目标是求解数据结构的一个操作序列中所执行的所有操作的平均时间，来评价操作的代价。与算法时间复杂度中的平均时间复杂度不同，这个平均代价与输入数据的分布无关，不是一个概率性的代价，而是用来衡量数据结构的操作性能的。

适用案例

在讨论具体的分析方法之前，先给出两个具体的问题。

栈的操作序列

考虑一个栈数据结构，可在上面执行三种操作，分别为压栈、弹出和连续弹出。

1
2
def Push(s, element):
    s.append(element)

1
2
def Pop(s):
    return s[-1]

1
2
3
4
def MultiPop(s, k):
    while not Empty(s) and k > 0:
        Pop(s)
        k = k - 1

有一个包含若干个上述操作的序列，操作总数为 \(n\)，目标是分析该序列的总代价的上界或每个操作的平均代价。

上述问题中，栈操作的代价可以很容易得出，即压栈、弹出和连续弹出的代价分别为 \(O(1)\)、\(O(1)\) 和 \(\min\{O(s), O(k)\}\)，其中 \(s\) 为栈的容量。

二进制计数器递增

考虑一个二进制计数器，计数器的初值为 \(0\)，用一个位数组 A[0...k - 1] 作为数据结构。数组的每个元素 A[i] 为 \(0\) 或 \(1\)，表示计数器内存储的数的二进制序列的第 \(i\) 位。具体地，若计数器的值为 \(x\)，则有

\[ x = \sum_{i = 0}^{k - 1} A[i] \times 2^i \]

计数器仅支持一个操作即为递增操作。

计数器递增
1
2
3
4
5
6
7
def Increment(A):
    i = 0
    while i < len(A) and A[i] == 1:
        A[i] = 0
        i = i + 1
    if i < len(A):
        A[i] = 1

目标是分析对计数器做 \(n\) 次递增操作的总代价的上界或每次操作的平均代价。

上述问题中，操作 Increment 的代价与翻转的位数呈线性关系。

聚合分析

聚合分析用来确定一个 \(n\) 个操作序列的总代价的上界 \(T(n)\)。因而每个操作的平均代价为 \(T(n) / n\)，作为每个操作的摊还代价。显然利用聚合分析得到的每个操作的摊还代价都是相等的。

栈操作

考虑一个由 \(n\) 个 Push、Pop 和 MultiPop 组成的序列在空栈上执行。一个重要的观察是序列中 Pop 的数量（包括 MultiPop 中调用的）最多和 Push 操作的数量相同，因为一个元素只能被弹出一次。设栈的容量为 \(n\)，则序列的总代价最多为 \(O(n)\)，从而每个操作的摊还代价为 \(O(n) / n = O(1)\)。

二进制计数器

在二进制计数器问题中，每次调用 Increment 操作，A[0] 都会被翻转一次，而 A[1] 没两次调用才翻转一次，A[2] 每四次调用翻转一次…… 从而对于一个初值为 \(0\) 的计数器，每 \(n\) 次 Increment 操作翻转的位数为

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

因此序列的总代价为 \(O(n)\)，Increment 的摊还代价为 \(O(n) / n = O(1)\)。

核算法

核算法用来分析每个操作的摊还代价，当存在不止一种操作时，每种操作的代价可能是不同的。核算法的思想是一种类似记账的方法，我们对不同操作赋予不同费用，赋予某些操作的费用可能多于或少于其实际代价，我们将赋予一个操作的费用称为它的摊还代价。

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

设 \(\hat{c}_i\) 和 \(c_i\) 为第 \(i\) 个操作的摊还代价和真实代价，要确保操作序列的总摊还代价是真实代价的上界，我们需保证

\[ \sum_{i = 1}^n \hat{c_i} \geqslant \sum_{i = 1}^n c_i \]

数据结构中储存的信用恰好等于总摊还代价与总实际代价的差值，即 \(\sum\limits_{i = 1}^n \hat{c_i} - \sum\limits_{i = 1}^n c_i\)。从而需要保证数据结构所关联的信用必须一直为非负值。

栈操作

回到栈操作序列的问题，我们可以为操作赋予这样的摊还代价：

Push            2
Pop             0
Multipop        0

这样的设置是显然的。每一次压栈时，由于摊还代价超出实际代价，缴纳一点代价的同时会存入一点信用以供弹出时使用，由于弹出的次数不可能多余压栈的次数，因此总的信用一定是非负的。

二进制计数器

考虑二进制计数器的问题，由于操作的运行时间与翻转的二进制位数成正比，我们可以翻转的位数看作操作的实际代价。

我们设置一次置位操作的摊还代价为 2，复位操作的摊还代价为 0(1)。这样的设置也是显然的，可以保证操作序列的总信用一定非负。

  1. 置位操作指从 \(0\) 变成 \(1\)，复位反之。

势能法

势能法摊还分析将预付代价表示为势能，将势能释放即可用来支付未来操作的代价。势能与整个数据结构绑定，而不是与特定对象关联。

如何理解“势能与整个数据结构绑定，而不是与特定对象关联”？

笔者的理解是，类比物理中的重力势能，势能由数据结构当前的状态决定，不与特定的对象绑定。举个例子，在核算法中，向栈中压入一个元素 \(x\)，这个元素就有了自己的信用，将来弹出这个元素时，用它的信用支付弹出该元素的费用，因此核算法中的信用是与特定对象绑定的。而势能则是整个数据结构的势能，不是某个对象的势能。

对一个初始数据结构 \(D_0\) 执行 \(n\) 个操作，令 \(c_i\) 为第 \(i\) 个操作的实际代价，则 \(D_i\) 为在数据结构 \(D_{i - 1}\) 上执行第 \(i\) 个操作的到的结果数据结构。

势函数 \(\varphi\) 将每个数据结构 \(D_i\) 映射到一个实数 \(\varphi(D_i)\) 上，为对应数据结构的势能。第 \(i\) 个操作的摊还代价 \(\hat{c}_i\) 用势函数定义为

\[ \hat{c}_i = c_i + \varphi(D_i) - \varphi(D_{i - 1}) \]

因此每个操作的摊还代价其实是其实际代价加上此操作引起的势能变化。由此得到操作序列的总摊还代价为

\[ \sum_{i = 1}^n \hat{c}_i = \sum_{i = 1}^{n} c_i + \varphi(D_n) - \varphi(D_0) \]

因此为了保证摊还代价为实际代价的上界，需要对任意的 \(i\)，有 \(\varphi(D_i) \geqslant \varphi(D_0)\)，通常情况下设 \(\varphi(D_0) = 0\)。

栈操作

再看栈操作序列，我们将势能函数定义为栈中元素的数量，从而有 \(\varphi(D_0) = 0\)，且 \(\varphi(D_i) \geqslant 0, \forall i\) 成立。下面计算各个操作的摊还代价：

\[ \begin{aligned} \hat{c}_i = c_i + \varphi(D_i) - \varphi(D_{i - 1}) = \begin{cases} 1 + 1 = 2 & \text{\verb|Push|} \\ 1 - 1 = 0 & \text{\verb|Pop|} \\ \min\{k, s\} - \min\{k, s\} = 0 & \text{\verb|MultiPop|} \end{cases} \end{aligned} \]

分析如之前的核算法一致。

二进制计数器

考虑将计数器执行 \(i\) 次 Increment 操作之后的势能定义为计数器中 1 的个数。假设第 \(i\) 个 Increment 操作将 \(t_i\) 个位复位，则其实际代价根据代码来看至多位 \(t_i + 1\)，因为最后要置位一次。

如果 \(\varphi(D_{i}) = 0\)，则第 \(i\) 个操作将所有的 \(k\) 位都复位了。显然说明第 \(i\) 次操作前，计数器的所有位都是 1，因此 \(\varphi(D_{i - 1}) = t_i = k\)；如果 \(\varphi(D_{i})> 0\)，则 \(\varphi(D_{i}) = \varphi(D_{i - 1}) - t_i + 1\)，无论何种情况

\[ \varphi(D_{i}) \leqslant \varphi(D_{i - 1}) - t_i + 1 \implies \varphi(D_{i}) - \varphi(D_{i - 1}) \leqslant 1 - t_i \]

因此摊还代价为

\[ \hat{c}_i = c_i + \varphi(D_i) - \varphi(D_{i - 1}) \leqslant t_i + 1 + 1 - t_i = 2 \]

且因为 \(\varphi(D_0) = 0\)，所以这个摊还分析可以给出一个总代价的上界。