6. 摊还分析¶

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

我们可以在无序数组中一串顺序查找的情形中运用摊还分析技巧。 对于 \(n\) 次随机查找，每次查找的平均情况代价 是 \(n/2\)，所以这一序列的 期望 总代价为 \(n^2/2\)。 不幸的是，在最坏情况下，所有查找都会 指向数组中的最后一项。 这种情况下，每次查找的代价是 \(n\)，总的最坏情况代价 为 \(n^2\)。 把它与这样一串 \(n\) 次查找的代价比较：数组中的每个 项恰好被查找一次。 在这种情况下，某些查找 必定 昂贵，但 某些查找也 必定 廉价。 对于这个问题，在最好、平均和最坏情况下，查找次数之和必定为 \(\sum_{i=i}^n i \approx n^2/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 循环后续还可执行的次数。

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

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