快速排序平均时间复杂度分析

对$x_1,\dots ,x_n$进行快速排序
partition node:$x[k]$为随机划分元
$x[k]$ 被选择的概率为 $1/n$,令 $C_n$ 为规模为n的问题的比较次数(即 $T(n)$ )
C n = ( n − 1 ) + 1 n ∑ k = 1 n ( C k − 1 + C n − k ) = ( n − 1 ) + 1 n ∑ k = 1 n C k − 1 + 1 n ∑ k = 1 n C n − k = ( n − 1 ) + 1 n ∑ k = 0 n − 1 C k + 1 n ∑ k = 0 n − 1 C k = ( n − 1 ) + 2 n ∑ k = 0 n − 1 C k Cn=(n−1)+1nn∑k=1(Ck−1+Cn−k)=(n−1)+1nn∑k=1Ck−1+1nn∑k=1Cn−k=(n−1)+1nn−1∑k=0Ck+1nn−1∑k=0Ck=(n−1)+2nn−1∑k=0Ck

Cn​​=(n−1)+n1​k=1∑n​(Ck−1​+Cn−k​)=(n−1)+n1​k=1∑n​Ck−1​+n1​k=1∑n​Cn−k​=(n−1)+n1​k=0∑n−1​Ck​+n1​k=0∑n−1​Ck​=(n−1)+n2​k=0∑n−1​Ck​​
因此
$$n{C}_n=n(n-1)+2\sum _{k=0}^{n-1}{C}_k①$$
用 $n-1$ 代入 $n$,得
$$(n-1)C_{n-1}=(n-1)(n-2)+2\sum _{k=0}^{n-2}{C}_k②$$
$①-②$ 得
$$\begin{array}{rl}& n{C}_n-(n-1)C_{n-1}=2(n-1)+2C_{n-1}\\ \Rightarrow & n{C}_n=2(n-1)+(n+1)C_{n-1}③\\ \Rightarrow & \frac{C_n}{n+1}=\frac{C_{n-1}}{n}+\frac{2(n-1)}{n(n+1)}\end{array}$$
令 $D_n=\frac{C_n}{n+1}$ 得
$$D_n=D_{n-1}+\frac{2(n-1)}{n(n+1)}④$$
因此
$$\begin{array}{rl}{D}_n& =2\sum _{j=1}^n\frac{j-1}{j(j+1)}\\ & =2\sum _{j=1}^n\frac{2}{j+1}-2\sum _{j=1}^n\frac{1}{j}\\ & =4\sum _{j=2}^{n+1}\frac{1}{j}-2\sum _{j=1}^n\frac{1}{j}\\ & =2\sum _{j=1}^n\frac{1}{j}+\frac{4}{n+1}-4\\ & =2H_n-\frac{4n}{n+1}\\ & \approx 2\ln n+O(1)\\ & =\frac{2}{{\log }_{2}e}{\log }_{2}n+O(1)\\ & \approx 1.44{\log }_{2}n\end{array}$$
因此
$$C_n\approx 1.44n{\log }_{2}n=O(n\log n)$$