3.11. 摊还分析¶

本模块介绍 摊还分析 的概念，它把一系列操作作为一个整体进行分析。特别是，摊还分析让我们能够处理这样的情形：\(n\) 个操作的最坏情况总成本小于 \(n\) 倍的单次操作最坏情况成本。摊还分析不是独立地关注每个操作的单个成本然后把它们加起来，而是考察整个序列的成本，并把总成本的一部分"分摊"（amortize）到每个单独操作上。

我们可以在无序数组中一串顺序查找的情形中运用摊还分析技巧。对于 \(n\) 次随机查找，每次查找的平均情况成本是 \(n/2\)，所以这一序列的 期望 总成本为 \(n^2/2\)。不幸的是，在最坏情况下，所有查找都会指向数组中的最后一项。这种情况下，每次查找的成本是 \(n\)，总的最坏情况成本为 \(n^2\)。把它与这样一串 \(n\) 次查找的成本比较：数组中的每个项恰好被查找一次。在这种情况下，某些查找 必定 昂贵，但某些查找也 必定 廉价。对于这个问题，在最好、平均和最坏情况下，查找次数之和必定为 \(\sum_{i=i}^n i \approx n^2/2\)。这比那种假设序列中每个操作都取其最坏情况成本的悲观分析成本减半。

作为摊还分析的另一个例子，考虑对二进制计数器进行递增的过程。该算法是从低位（最右端）位向高位（最左端）移动，把 1 改为 0，直到遇到第一个 0。把这个 0 改为 1，递增操作就完成了。下面是递增操作的一种实现，假设长度为 \(n\) 的二进制数存放在长度为 \(n\) 的数组 A 中。

// Increment a binary countery
for (i=0; ((i<A.length) && (A[i] == 1)); i++) {
  A[i] = 0;
}
if (i < A.length) {
  A[i] = 1;
}

如果我们从 0 数到 \(2^n - 1\) （需要一个至少 \(n\) 位的计数器），那么一次递增操作的平均成本（以被处理的位数计）是多少？朴素的最坏情况分析认为，如果所有 \(n\) 位都是 1 （除了最高位），那么需要处理 \(n\) 位。因此，如果有 \(2^n\) 次递增，那么成本为 \(n 2^n\)。然而，这高估得太多，因为处理这么多位是很少见的。事实上，有一半的时间最低位都是 0，所以只有那一位被处理。有四分之一的时间，低位两位是 01，所以只有低位两位被处理。看待这一点的另一种方式是：最低位总是被翻转，其左边的位有一半时间被翻转，再下一个位有四分之一的时间被翻转，依此类推。我们可以用这个求和来刻画这一点（成本从右到左分摊到各低位上）

换句话说，每次递增被翻转的位的平均数为 2，因此一次 \(2^n\) 次递增的系列总成本只有 \(2 \cdot 2^n\)。

栈数据结构的一个简单变体说明了摊还分析的一个有用概念：把 pop 函数稍作修改，额外的参数 \(k\) 表示要执行 \(k\) 次出栈操作。

对 multipop 的"局部"最坏情况分析是 \(\Theta(n)\)，其中 \(n\) 是栈中的元素个数。因此，如果有 \(m_1\) 次 push 调用和 \(m_2\) 次 multipop 调用，那么这一系列操作的朴素最坏情况成本为 \(m_1 + m_2\cdot n = m_1 + m_2 \cdot m_1\)。这个分析不合理地悲观。显然，不可能每次 multipop 被调用都真正弹出 \(m_1\) 个。只关注单个操作的分析无法处理这种全局性限制，所以为了对这一整串操作建模，我们转而求助于摊还分析。

这个问题摊还分析的关键在于 势 的概念。在任何给定时刻，栈上可能有若干项。 multipop 的成本不可能超过这一项数。每次 push 调用把一个额外项压入栈中，它可能被一次 multipop 操作移除。因此，每次 push 调用都会把栈的势提高一个项。所有 multipop 调用的成本之和绝不会超过栈的总势（此外还有与每次 multipop 调用本身相关的常数时间成本）。

任意一串 push 和 multipop 操作的摊还成本是三项成本之和。第一，每次 push 操作都花常数时间。第二，每次 multipop 操作都要花一个常数时间的额外开销，无论该调用弹出了多少项。最后，我们计入所有 multipop 操作消耗的势之和，它至多为 \(m_1\)，即 push 操作的次数。因此这个总成本可以表示为

在 快速排序 算法的分区函数分析中，我们也使用了类似的论证。 虽然在任何给定的一趟 while 循环中，左或右 指针都可能一直移动穿过分区剩余的部分，但这样做 会减少 while 循环后续还可执行的次数。

我们的最后一个例子用摊还分析来证明 前移 自组织线性表启发式的成本与线性表最优静态排序成本之间的关系。 在下面的讨论中，我们 假设所有查找都是成功的 （也就是说，所有查找都要找包含在线性表中的记录）。

对于一串查找操作，如果记录按访问频率排列，不变线性表就能取得最小成本。如果我们从不允许记录的位置变动，那么这就是记录的最优排列，因为最常被访问的记录排在最前（因此成本最小），接下来是次常被访问的记录，依此类推。