10.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}\) 次中失败一次，这比你能想象到的、任何可能干扰这一过程的合理灾难的概率还要小。