3.1. 概率算法¶

我们现在来考虑，在算法中引入随机性如何 可能加快速度，尽管也许是以准确性为代价。 但我们常常可以把误差的概率或大小 降低到任意低的程度，同时仍然加快算法的速度。 求最大值是说明我们可能愿意接受这种灵活性 的一个好例子。 在无序线性表中求最大值的下界是 \(\Omega(n)\)。 这是要 确定 我们找到了最大值的 最短所需时间。 但如果我们愿意放宽对确定性的要求呢？ 第一个问题是：这是什么意思？ "确定性"有很多方面，我们可能以各种方式 放宽这一要求。

要求一个以 \(X\) 作为最大值输出的算法， 可能提供若干种保证，其中真实最大值是 \(Y\)。

• 到目前为止，我们一直假设要求 \(X\) 等于 \(Y\)。 这被称为求解该问题的精确算法或 确定性算法。

• 我们可以放宽这个要求，只要求 \(X\) 的秩（在 有序线性表中的排名）"接近" \(Y\) 的秩 （也许在某个固定距离或百分比之内）。 这被称为 近似算法。

• 我们可以要求 \(X\) "通常"是 \(Y\)。 这被称为 概率算法。

• 最后，我们可以只要求 \(X\) 的秩"通常" "接近" \(Y\) 的秩。 这被称为 启发式算法。

我们还可能选择以不同的方式牺牲可靠性换取速度。 这类算法也有名字。

1. 拉斯维加斯算法： 我们总能找到最大值，而且"通常"能很快找到它。 这类算法有保证的结果，但不保证 快速运行时间。

2. 蒙特卡罗算法： 我们很快找到最大值，或者根本得不到答案 （但还是很快）。 虽然这类算法有良好的运行时间，但它们的结果 没有保证。

这里有一个寻找大值的算法示例，它放弃 获得最优值的保证，以换取改进的运行时间。 这是一个 概率算法 的例子，因为它 包含受随机事件影响的步骤。 随机选择 \(m\) 个元素，把其中最好的一个 作为答案。 对大的 \(n\)，如果 \(m \approx \log n\)，答案就相当不错。 代价是 \(m-1\) 次比较（因为我们必须在 \(m\) 个值中 找最大值）。 但我们不确定会得到什么。 不过，我们可以估计它的秩将约为 \(\frac{mn}{m+1}\)。 例如，如果 \(n = 1,000,000\) 且 \(m = \log n = 20\)， 那么我们期望这 20 个随机选取的值中最大的一个 位于这 \(n\) 个值的前 5% 之内。

接下来，考虑一个稍有不同的问题，目标是 在 \(n\) 个值的上半部分中选一个数。 我们将在前 \(\frac{n+1}{2}\) 个值中选最大值， 代价是 \(n/2\) 次比较。 我们能做得比这更好吗？ 如果我们想保证得到正确答案，那不能。 但如果愿意接受"接近确定"而不是"绝对确定"， 我们在速度上就能获得很多。

作为替代，考虑下面这个概率算法。 选 2 个数，取较大者。 它以 3/4 的概率位于上半部分（因为它只在两个数 都碰巧位于下半部分时才不处于上半部分）。 3/4 的概率还不够好吗？ 那我们再多选一些数！ 对 \(k\) 个数，最大值位于上半部分的概率是 \(1 - \frac{1}{2^k}\)，与我们从中选取的数值 \(n\) 无关，只要 \(n\) 远大于 \(k\) （否则概率甚至可能变得更高）。 如果我们选十个数，那么失败的概率只有 \(2^{10} = 1024\) 分之一。 如果我们真的一心想确定，因为生命取决于从上半部分选出 一个数呢？ 如果我们选 30 个数，十亿次里只能失败一次。 如果我们选足够多的数，那么选到小数的 概率比计算过程中电源失效的概率还要小。 选 100 个数意味着我们只在 \(2^{100}\) 次中失败一次，这比你能想象到的、 任何可能干扰这一过程的合理灾难的概率还要小。