2.3.14 #

解答 #

中文版题目有误，详见官方勘误页面

假设 $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})\newline &=\sum_{i=1}^{n}2(\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n-i+1}) \newline &<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 - 卡内基梅隆大学 如果还是不能理解为什么多次切分不影响概率，可以参考三门问题的解释： 蒙提霍尔问题 - 维基百科 蒙提霍尔问题（又称三门问题、山羊汽车问题）的正解是什么？- 知乎