2.3.14

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

中文版题目有误,详见官方勘误页面:https://algs4.cs.princeton.edu/errata/errata-printing3.php

假设 $ i < j​$ 。
首先,在快速排序中,如果两个元素要发生交换,意味着其中一个元素被选为枢轴。
而且数组中的元素各不相同,那么两个特定的元素的比较最多发生一次。

那么先考虑一个特殊情况,$ i = 1, j = n $ ,即求最大值和最小值比较的概率。
此时,一旦枢轴不是这两个元素之一,
最大值和最小值会被分到两个不同的子数组,无法发生比较。
因此在这种特例下第 $ i $ 大的元素和第 $ j $ 大的元素发生比较的概率为 $ \frac{2}{n} = \frac{2}{j-i+1} $ 。

接下来考虑一般情况,如果枢轴选择了第 $ i $ 到第 $ j $ 大之外的元素,
那么第 $ i $ 大和第 $ j $ 大的元素会被分到同一个子数组里,重复上述过程。
因此我们所求的概率只和从第 $ i $ 大到第 $ j $ 大之间的元素有关,概率为 $\frac{2}{j-i+1}$。
(举个例子,一个箱子里有 2 个红球、1个蓝球和 7 个白球,现在摸球而不放回。
如果摸到白球可以再摸一次,直到摸到红球或蓝球为止。
显然在这样的规则下摸到红球或蓝球的概率为 1,即白球对概率没有影响。)

现在我们已经得到了某两个元素比较的概率 $E(X_{ij})$,接下来我们求每两个元素比较的概率 $ E(X) $。
$$
\begin{align}
E(X)
&= \sum_{i=1}^{n}\sum_{j=i+1}^{n}E(X_{ij})\\
&=\sum_{i=1}^{n}2(\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n-i+1}) \\
&<2n(\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n})
\end{align}
$$
根据调和级数的性质($ \ln (n) < 1+ \frac{1}{2}+ \cdots + \frac{1}{n} < 1+\ln(n) $),可以得到结论:
$$
E(X) < 2n \ln(n)
$$

另请参阅

下面这个链接里的 3.4.2 节给出了解法。
lect0906 - 卡内基梅隆大学
如果还是不能理解为什么多次切分不影响概率,可以参考三门问题的解释:
蒙提霍尔问题 - 维基百科
蒙提霍尔问题(又称三门问题、山羊汽车问题)的正解是什么?- 知乎

上一题 下一题