1. 求最大值¶

1.1. 求最大值¶

如何在有序线性表中找出第 \(i\) 大的值？显然，我们只需走到第 \(i\) 个位置即可。但如果是无序线性表呢？我们能做得比排序更好吗？如果我们要找的是最小值或最大值，当然可以做得比给线性表排序更好。对第二大的值呢？对中位数呢？在后面的小节中，我们将考察这些问题。在本节，我们将通过重新审视在无序线性表中求最大值这个简单问题，继续我们对下界证明的考察。

下面是一个求最大值的简单算法。

Java
C++

    // Return position of largest value in integer array A
    static int largest(int[] A) {
        int currlarge = 0;             // Position of largest element seen
        for (int i=1; i<A.length; i++) // For each element
            if (A[currlarge] < A[i])     //   if A[i] is larger
                currlarge = i;            //     remember its position
        return currlarge;              // Return largest position
    }

/** Return position of largest value in integer array A */
int largest(int A[], int size) {
  int currlarge = 0;             // Position of largest element seen
  for (int i=1; i<size; i++)     // For each element
    if (A[currlarge] < A[i])     //   if A[i] is larger
       currlarge = i;            //     remember its position
  return currlarge;              // Return largest position
}

显然，这个算法需要 \(n\) 次比较。这是最优的吗？凭直觉它显然是最优的，但让我们尝试证明它。（在继续阅读之前，你可以先试着写下自己的证明。）

这个证明显然是错误的，因为胜者并不需要显式地与所有其他元素比较就能被确认。例如，一场标准的单淘汰制体育锦标赛只需要 \(n-1\) 次比赛，而胜者并不需要每场都打遍所有对手。所以我们再试一次。

这个证明是可靠的。不过，稍后我们通过引入偏序集的概念来抽象它是有用的。我们可以把求最大值问题看作从一个没有任何已知关系的偏序集开始，因此集合中的每个成员都各自处于一个仅含单个元素的有向无环图（DAG）中。

largest 的平均代价是多少？由于它总是做相同次数的比较，显然它的代价必然是 \(n-1\) 次比较。我们还可以考虑 largest 必须进行的赋值次数。函数 largest 可能在 for 循环的任何一次迭代中执行一次赋值。

因为这一事件要么发生，要么不发生，如果我们对分布一无所知，可以猜测每次比较之后以二分之一的概率做一次赋值。但这显然是错误的。事实上，当且仅当 A [\(i\)] 是前 \(i\) 个元素中最大的时候， largest 才会在第 \(i\) 次迭代做一次赋值。假定所有排列等可能，这一事件为真的概率是 \(1/i\) 。因此，平均所做的赋值次数为

\[1 + \sum_{i=2}^n \frac{1}{i} = \sum_{i=1}^n \frac{1}{i}\]

这就是调和级数（Harmonic Series） \({\cal H}_n\) 。

\[{\cal H}_n = \Theta(\log n).\]

更准确地说， \({\cal H}_n\) 接近 \(\log_e n\) 。

这个平均值有多"可靠"？也就是说，程序的一次给定运行会在多大程度上偏离平均代价？根据切比雪夫不等式（Chebysev's Inequality），一次观测落在均值两个标准差以内的概率至少有 75%。对于 Largest ，方差为

\[{\cal H}_n - \frac{\pi^2}{6} = \log_e n - \frac{\pi^2}{6}.\]

因此标准差约为 \(\sqrt{\log_e n}\) 。所以，75% 的观测值介于 \(\log_e n - 2\sqrt{\log_e n}\) 与 \(\log_e n + 2\sqrt{\log_e n}\) 之间。这是窄分布还是宽分布？与均值相比，这个分布相当宽，意味着赋值的次数在程序的各次运行之间变化很大。下面是一些取值：

对 \(n = 100\) ， 75% 的值落在 \(4.605 \pm 4.30\) 的范围内（所以有 25% 离均值甚至更远）
对 \(n = 1000\) ， 75% 的值落在 \(6.908 \pm 5.26\) 的范围内。
对 \(n = 1,000,000\) ， 75% 的值落在 \(13.816 \pm 7.43\) 的范围内。

1.2. 鸣谢¶

本页大量借用 Gregory J.E. Rawlins 所著 Compared to What? 第 3.2 节的内容。

OpenDSA 完整目录

Chapter 23 Lower Bounds

1. 求最大值¶

1.1. 求最大值¶

1.2. 鸣谢¶