3. 状态空间下界证明¶

现在我们来考虑这样一个问题：从一个（无序的）值线性表中同时找出最小值和最大值。 如果我们想了解一组待绘制的值的取值范围，以便绘制图表坐标轴的标度，这可能会很有用。 当然，我们可以分别求出它们，需要 \(2n-2\) 次比较。 稍加修改的做法是：用 \(n-1\) 次比较找出最大值，把它从线性表中移出，然后再用 \(n-2\) 次比较找出最小值，总共 \(2n-3\) 次比较。 我们能做得比这更好吗？

在继续之前，思考片刻：这个求最小值和最大值的问题，与上一节求第二大的值（并隐含最大值）的问题相比，哪一个更难？ 你可能完全不觉得其中一个比另一个更难或更容易。 两种直觉各自支持一种结论。 一方面，直觉可能认为求最大值的过程告诉你的关于第二大值的信息，应该多于它告诉你的关于最小值的信息。 另一方面，任何给定的比较都会告诉你哪一个可能是最大值的候选者、哪一个可能是最小值的候选者，从而在两个方向上都取得进展。

我们将先考虑一种简单的分治方法，来求最小值和最大值。 把线性表分成两部分，分别找出各部分中的最小和最大元素。 然后，用另外两次比较把两个最小值和两个最大值分别进行比较，得到最终结果。 算法如下：

// Return the minimum and maximum values in A between positions l and r
void MinMax(int A[], int l, int r, int Out[]) {
  if (l == r) {        // n=1
    Out[0] = A[r];
    Out[1] = A[r];
  }
  else if (l+1 == r) { // n=2
    Out[0] = Math.min(A[l], A[r]);
    Out[1] = Math.max(A[l], A[r]);
  }
  else {               // n>2
    int[] Out1 = new int[2];
    int[] Out2 = new int[2];
    int mid = (l + r)/2;
    MinMax(A, l, mid, Out1);
    MinMax(A, mid+1, r, Out2);
    Out[0] = Math.min(Out1[0], Out2[0]);
    Out[1] = Math.max(Out1[1], Out2[1]);
  }
}

这个算法的代价可以用下面的递推关系来建模。

这是一个相当有趣的递推关系，因为我们可以认为它有一族闭式解。 首先让我们在 \(n = 2^k\) 的情况下求解。

让我们把递推关系展开一点。

我们可以继续展开得到最终的闭式解：

但输入并不总是 2 的幂，而这确实有影响。 看待这个问题的一种方式是：当代价取 \(n/2\) 的下取整时，奇数的输入规模有帮助；但当代价取 \(n/2\) 的上取整时，它反而有害。 如果你总是两者都取，也许就没关系了。 但在本例中，我们在实践中最终总是一个取上取整、一个取下取整，这意味着代价可能会变化。 考虑下面这个：

$f(n)$ 的真实代价介于 \(3n/2 - 2\) （当 \(n = 2^i\) 或 \(n=2^1 \pm 1\) 时）与 \(5n/3 - 2\) （当 \(n = 3 \times 2^i\) 时）之间。 我们可以从这一行为推断出：如何划分线性表会影响算法的性能。 例如，如果线性表中有六个元素会怎样？ 如果把线性表分成两个各含三个元素的子线性表，代价是 8。 如果把它分成一个含两个元素、另一个含四个元素的子线性表，代价就只有 7。

对于分治法，最好的算法是使工作量最小的算法，而不一定是使输入规模均衡的算法。 从这个例子中要学到的教训之一是：注意 \(n\) 较小时发生的情况可能很重要，因为对线性表的任何划分最终都会产生许多小线性表。

对这个问题所有可能的分治策略，我们都可以用下面的递推关系来计算最小值。

也就是说，我们希望找到一种划分线性表的方式，使总工作量最小。 考察几个小规模情形下会发生什么，或许会有帮助。

如果我们考察各种划分小线性表的方式，最终会认识到：把线性表划分成一个大小为 2 的子线性表和一个大小为 (n-2) 的子线性表，总是能产生与任何其他划分一样好的结果。 这一策略产生如下递推关系。

这个递推关系（以及相应的算法）产生 \(\mathbf{T}(n) = \lceil 3n/2 \rceil - 2\) 次比较。 这是最优的吗？ 现在我们向下界证明技巧的宝库中再引入一件工具：状态空间证明。

我们将这样对算法建模：定义一个算法在任意给定时刻所处的 状态 。 然后定义起始状态、结束状态，以及任何算法都能支持的状态间转移。 由此，我们将推导算法从起始状态到结束状态必须经过的最少状态数，从而得到一个状态空间下界。

在任意给定时刻，我们可以根据元素先前的比较历史，跟踪以下四类元素：

• 未测试：尚未比较过的元素。

• 胜者：至少赢过一次比较、且从未输过的元素。

• 败者：至少输过一次比较、且从未赢过的元素。

• 中间状态：既赢过也输过至少一次的元素。

我们把当前状态定义为一个四元向量 \((U, W, L, M)\) ，分别表示未测试、胜者、败者和中间状态元素的个数。 对于一组 \(n\) 个元素，算法的初始状态是 \((n, 0, 0, 0)\) ，结束状态是 \((0, 1, 1, n-2)\) 。 因此，任何算法的每次运行都必须从状态 \((n, 0, 0, 0)\) 到达状态 \((0, 1, 1, n-2)\) 。 我们还观察到，一个元素一旦被认定为中间状态，就可以被忽略，因为它既不可能成为最小值，也不可能成为最大值。

既然有四种类型的元素，就有 10 种类型的比较。 与处于中间状态的元素比较，不可能比其他比较更高效，所以我们应该忽略这些。 于是剩下六种我们关心的比较类型。 我们可以如下列举每种比较类型的效果。 如果我们在状态 \((i, j, k, l)\) 上进行一次比较，则状态变化如下。

现在，让我们运用对手概念，考虑各种比较时对手会怎么做。 对手会确保每次比较在推动算法走向目标状态时只做尽可能少的工作。 例如，把胜者与败者比较没有价值，因为最坏情况下结果总是学不到任何新东西（胜者仍是胜者，败者仍是败者）。 我们也可能会把未测试元素与胜者或败者比较（如果竞争者数目为奇数就必须如此），但对手绝不会选择增加中间状态数目的那种做法。 因此，只有下面五种转移值得关注：

在表中，我们把增加中间状态数目的转移与不增加的转移分开，因为那是整个过程中的关键部分。 只有最后两种转移会增加中间状态的数目，每次增加一个，所以必须有 \(n-2\) 次这样的比较。 未测试元素的数目必须归零，而第一种转移是做到这一点的最有效方式。 因此，需要 \(\lceil n/2 \rceil\) 次这样的转移。 我们的结论是：最少可能的状态转移（比较）次数是 \(n + \lceil n/2 \rceil - 2\) 。 这就给出了一个简单的最优算法：

• 首先，把所有输入两两配对并比较，产生胜者和败者。

• 然后，把胜者与胜者、败者与败者比较，产生 \(n-2\) 个中间状态元素。