2.3.13

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 页找到。

QuickSort-纽约大学

《算法导论》中关于随机 BST 高度的证明(P321 Theorem12.4)

Introduction to Algorithms

也可以参考下面这个链接获得更详细的解释。

Proof that a randomly built binary search tree has logarithmic height-StackExchange