2.3.13

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

解答

快速排序先将数组分为 (小于枢轴)枢轴(大于枢轴)三部分,然后再分别递归的排序左右两部分数组。
在这里,我们可以将快速排序的递归树看作是一棵二叉搜索树(BST, Binary Search Tree)。
枢轴作为根结点,左子树即为左数组构造的 BST,右子树即为右数组构造的 BST。
这样题目中所求的递归深度即为所构造的 BST 的高度。

最坏情况,每次都只有枢轴和大于枢轴两部分,BST 退化为链表,高度为 $ n-1 $。

最好情况,每次枢轴都正好平分数组,构造一棵完全二叉树,高度为 $ \log n $。

平均情况,问题转化为:一个由 $ n $ 个元素随机构造的 BST 的平均高度是多少?
《算法导论》给出的结论是 $ \log n $ ,具体证明如下:
设由 $ n $ 个结点随机构成的 BST 的高度为 $ h_n $,那么有:
$$
h_n=1+\max(h_{l}+h_{r})
$$
其中,$ h_l $ 和 $ h_r $ 分别代表左数组和右数组构造的 BST 的高度。
设枢轴位置为 $ i $,上式可简化为:
$$
h_n=1+\max(h_{i-1}, h_{n-i})
$$
由于枢轴位置可以在 1~n 之间任意取值且概率相等,因此 BST 的平均高度(即高度的期望)为:
$$
E(h_n)=\frac{1}{n}\sum_{i=1}^{n}\lbrack 1+\max(h_{i-1}, h_{n-i}) \rbrack
$$
我们令 $ Y_n=2^{h_n} $,可得:
$$
Y_n=2\times\max(Y_{i-1},Y_{n-i})
$$
我们把 $ Y_n $ 代入,可得:
$$
\begin{aligned}
E(Y_n)
&=\sum_{i=1}^{n}\frac{1}{n}E\lbrack2\times\max(Y_{i-1}, Y_{n-i})\rbrack\\
&=\frac{2}{n}\sum_{i=1}^{n}E\lbrack\max(Y_{i-1},Y_{n-i})\rbrack\\
\end{aligned}
$$
接下来我们去掉最大值运算,根据最大值的性质,下式显然成立:
$$
E\lbrack\max(X,Y)\rbrack\le E\lbrack\max(X,Y)+\min(X,Y)\rbrack=E\lbrack X+Y\rbrack=E\lbrack X\rbrack+E\lbrack Y\rbrack
$$
代入可得:
$$
E(Y_n)
\le\frac{2}{n}\sum_{i=1}^{n}(E\lbrack Y_{i-1}\rbrack + E\lbrack Y_{n-i} \rbrack)
=\frac{2}{n}\sum_{i=0}^{n-1}2E\lbrack Y_i\rbrack
=\frac{4}{n}\sum_{i=0}^{n-1}E\lbrack Y_i\rbrack
$$
大小为 0 的数组构成的 BST 的高度显然为 0,我们设 $ Y_0=0 $ 。接下来用一个组合数公式来构造上界:
$$
\begin{align}
0&=Y_0=E\lbrack Y_0 \rbrack\le \frac{1}{4}\begin{pmatrix}3\\3\end{pmatrix}=\frac{1}{4}\\
1&=Y_1=E\lbrack Y_1 \rbrack\le\frac {1}{4}\begin{pmatrix}3+1\\3\end{pmatrix}=1 \\
\vdots \\
Y_i &=E\lbrack Y_i\rbrack\le\frac{1}{4}\begin{pmatrix}i+3\\3\end{pmatrix}
\end{align}
$$
注意这里的组合数公式为:
$$
\begin{pmatrix}n\\r\end{pmatrix}=\frac{r!}{r!(n-r)!}
$$
代入可得:
$$
\begin{align}
E(Y_n) &\le \frac{4}{n}\sum_{i=0}^{n-1}E\lbrack Y_i\rbrack \\
&\le\frac{4}{n}\sum_{i=0}^{n-1}\frac{1}{4}\begin{pmatrix}i+3\\3\end{pmatrix} \\
&=\frac{1}{n}\sum_{i=0}^{n-1}\begin{pmatrix}i+3\\3\end{pmatrix}
\end{align}
$$
接下来我们去掉求和符号,首先根据组合数的性质,有以下等式成立
$$
\begin{align}
\begin{pmatrix}n\\k\end{pmatrix}&=\begin{pmatrix}n-1\\k-1\end{pmatrix}+\begin{pmatrix}n-1\\k\end{pmatrix} \\
\begin{pmatrix}n\\n\end{pmatrix}&=1
\end{align}
$$
我们把求和式展开得到:
$$
\begin{align}
\sum_{i=0}^{n-1}\begin{pmatrix}i+3\\3\end{pmatrix}
&=\begin{pmatrix}3\\3\end{pmatrix} + \begin{pmatrix}4\\3\end{pmatrix}+\cdots+\begin{pmatrix}n+2\\3\end{pmatrix} \\
&=\begin{pmatrix}4\\4\end{pmatrix} + \begin{pmatrix}4\\3\end{pmatrix}+\cdots+\begin{pmatrix}n+2\\3\end{pmatrix} \\
&=\begin{pmatrix}n+3\\4\end{pmatrix}
\end{align}
$$
代入可得:
$$
\begin{align}
E(Y_n) &\le\frac{1}{n}\sum_{i=0}^{n-1}\begin{pmatrix}i+3\\3\end{pmatrix}\\
&=\frac{1}{n}\begin{pmatrix}n+3\\4 \end{pmatrix} \\
&=\frac{1}{n}\cdot\frac{(n+3)!}{4!(n-1)!} \\
&=\frac{1}{4}\cdot\frac{(n+3)!}{3!n!} \\
&=\frac{(n+1)(n+2)(n+3)}{24} \\
&=\frac{n^3+6n^2+11n+6}{24}
\end{align}
$$
由于 $Y_n=2^{h_n}$ ,因此 $E\lbrack Y_n \rbrack=E\lbrack 2^{h_n} \rbrack$。
由于 $f(x)=2^x$ 是个凸函数,可以应用延森不等式(凸函数的割线一定在函数上方),即 $2^{E\lbrack h_n\rbrack}\le E\lbrack Y_n\rbrack$。
于是得到结论:
$$
2^{E\lbrack h_n\rbrack} \le \frac{n^3+6n^2+11n+6}{24} \\
E\lbrack h_n \rbrack\le \log(\frac{n^3+6n^2+11n+6}{24})
$$

另请参阅

快速排序的递归树可以视为 BST 的结论可以在下面这个 PPT 的第 5 页找到。
QuickSort-纽约大学
《算法导论》中关于随机 BST 高度的证明(P321 Theorem12.4)
Introduction to Algorithms
也可以参考下面这个链接获得更详细的解释。
Proof that a randomly built binary search tree has logarithmic height-StackExchange

上一题 下一题