条件期望4

条件期望例题----快排算法的分析

快速排序算法的递归定义如下:
有n个数($n\ge 2$), 一开始随机选取一个数$x_i$, 并将$x_i$和其他n-1个数进行比较, 记$S_i$为比$x_i$小的元素构成的集合, $\overline{S_i}$为比$x_i$大的元素构成的集合, 然后分别对$S_i$和$\overline{S_i}$进行排序.
如果集合中元素个数等于2, 则简单比较即可, 如果大于2, 则重复上述过程.
我们选取整个排序过程中的比较次数的期望作为算法效率分析的指标. 记$M_n$为在n个不同元素的集合中, 实行快速排序算法所需要的比较次数的均值, 易知$M_0=M_1=0,M_2=0.5$.
易知
$$M_n=\sum _{j=1}^{n}E[比较次数|初始随机取的元素为集合中的第j个值]\frac{1}{n}$$
如果初始选的值是所有元素中第$j$小的, 则对应的$S$集合就有$j-1$个元素, $\bar{S}$就有n-j个元素, 因为第一次选取之后一定会比较$n-1$次, 所以可得
$$\begin{array}{rl}{M}_n& =\sum _{j=1}^n(n-1+M_{j-1}+M_{n-j})\frac{1}{n}\\ & =n-1+\frac{1}{n}\sum _{k=1}^{n-1}{M}_k+\frac{1}{n}\sum _{m=n-1}^1{M}_m\\ & =n-1+\frac{2}{n}\sum _{k=1}^{n-1}{M}_k\end{array}$$
所以
$$n{M}_n=n(n-1)+2\sum _{k=1}^{n-1}{M}_k$$
易知
$$(n+1)M_{n+1}=n(n+1)+2\sum _{k=1}^n{M}_k$$
所以
$$(n+1)M_{n+1}-n{M}_n=n(n-1)=2n+2M_n$$
即
$$(n+1)M_{n+1}=2n+(n+2)M_n$$
所以
$$M_{n+1}=\frac{2n}{n+1}+\frac{n+2}{n+1}{M}_n$$

两边同除以$(n+2)$, 有
$$\frac{M_{n+1}}{n+2}=\frac{2n}{(n+1)(n+2)}+\frac{M_n}{n+1}$$
迭代这个过程, 有
$$\begin{array}{rl}\frac{M_{n+1}}{n+2}& =\frac{2n}{(n+1)(n+2)}+\left(\frac{2(n-1)}{n(n+1)}+\frac{M_{n-1}}{n}\right)\\ & =\cdots \\ & =2\sum _{k=0}^{n-1}\frac{n-k}{(n+1-k)(n+2-k)}\\ & (M_1=0)\end{array}$$
所以
$$\begin{array}{rl}{M}_{n+1}& =2(n+2)\sum _{i=1}^n\frac{i}{(i+1)(i+2)}\\ & (i=n-k)\\ & =2(n+2)\left[\sum _{i=1}^n\frac{2}{i+2}-\sum _{i=1}^n\frac{1}{i+1}\right]\\ & \approx 2(n+2)\left[{\int }_3^{n+2}\frac{2}{x}dx-{\int }_2^{n+1}\frac{1}{x}dx\right]\\ & (步长为1的数值积分)\\ & \approx 2(n+2)ln(n+2)\end{array}$$