2.3.13 #
解答 #
快速排序先将数组分为 （小于枢轴）枢轴（大于枢轴）三部分，然后再分别递归的排序左右两部分数组。
在这里，我们可以将快速排序的递归树看作是一棵二叉搜索树（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\newline &=\frac{2}{n}\sum_{i=1}^{n}E\lbrack\max(Y_{i-1},Y_{n-i})\rbrack\newline \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\newline 3\end{pmatrix}=\frac{1}{4}\newline 1&=Y_1=E\lbrack Y_1 \rbrack\le\frac {1}{4}\begin{pmatrix}3+1\newline 3\end{pmatrix}=1 \newline \vdots \newline Y_i &=E\lbrack Y_i\rbrack\le\frac{1}{4}\begin{pmatrix}i+3\newline 3\end{pmatrix} \end{align} $$
注意这里的组合数公式为：
$$ \begin{pmatrix}n\newline 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 \newline &\le\frac{4}{n}\sum_{i=0}^{n-1}\frac{1}{4}\begin{pmatrix}i+3\newline 3\end{pmatrix} \newline &=\frac{1}{n}\sum_{i=0}^{n-1}\begin{pmatrix}i+3\newline 3\end{pmatrix} \end{align} $$
接下来我们去掉求和符号，首先根据组合数的性质，有以下等式成立
$$ \begin{align} \begin{pmatrix}n\newline k\end{pmatrix}&=\begin{pmatrix}n-1\newline k-1\end{pmatrix}+\begin{pmatrix}n-1\newline k\end{pmatrix} \newline \begin{pmatrix}n\newline n\end{pmatrix}&=1 \end{align} $$
我们把求和式展开得到：
$$ \begin{align} \sum_{i=0}^{n-1}\begin{pmatrix}i+3\newline 3\end{pmatrix} &=\begin{pmatrix}3\newline 3\end{pmatrix} + \begin{pmatrix}4\newline 3\end{pmatrix}+\cdots+\begin{pmatrix}n+2\newline 3\end{pmatrix} \newline &=\begin{pmatrix}4\newline 4\end{pmatrix} + \begin{pmatrix}4\newline 3\end{pmatrix}+\cdots+\begin{pmatrix}n+2\newline 3\end{pmatrix} \newline &=\begin{pmatrix}n+3\newline 4\end{pmatrix} \end{align} $$
代入可得：
$$ \begin{align} E(Y_n) &\le\frac{1}{n}\sum_{i=0}^{n-1}\begin{pmatrix}i+3\newline 3\end{pmatrix}\newline &=\frac{1}{n}\begin{pmatrix}n+3\newline 4 \end{pmatrix} \newline &=\frac{1}{n}\cdot\frac{(n+3)!}{4!(n-1)!} \newline &=\frac{1}{4}\cdot\frac{(n+3)!}{3!n!} \newline &=\frac{(n+1)(n+2)(n+3)}{24} \newline &=\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} \newline E\lbrack h_n \rbrack\le \log(\frac{n^3+6n^2+11n+6}{24}) $$
另请参阅 #
快速排序的递归树可以视为 BST 的结论可以在下面这个 PPT 的第 5 页找到。
《算法导论》中关于随机 BST 高度的证明（P321 Theorem12.4）
也可以参考下面这个链接获得更详细的解释。
Proof that a randomly built binary search tree has logarithmic height-StackExchange