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

快速排序算法的递归定义如下:
有n个数(n≥2n\geq 2n≥2), 一开始随机选取一个数xix_ixi​, 并将xix_ixi​和其他n-1个数进行比较, 记SiS_iSi​为比xix_ixi​小的元素构成的集合, Siˉ\bar{S_i}Si​ˉ​为比xix_ixi​大的元素构成的集合, 然后分别对SiS_iSi​和Siˉ\bar{S_i}Si​ˉ​进行排序.
如果集合中元素个数等于2, 则简单比较即可, 如果大于2, 则重复上述过程.
我们选取整个排序过程中的比较次数的期望作为算法效率分析的指标. 记MnM_nMn​为在n个不同元素的集合中, 实行快速排序算法所需要的比较次数的均值, 易知M0=M1=0,M2=0.5M_0 = M_1 = 0, M_2 = 0.5M0​=M1​=0,M2​=0.5.
易知
Mn=∑j=1nE[比较次数∣初始随机取的元素为集合中的第j个值]1nM_n = \sum_{j=1}^nE[比较次数|初始随机取的元素为集合中的第j个值]\frac{1}{n} Mn​=j=1∑n​E[比较次数∣初始随机取的元素为集合中的第j个值]n1​
如果初始选的值是所有元素中第jjj小的, 则对应的SSS集合就有j−1j-1j−1个元素, Sˉ\bar{S}Sˉ就有n-j个元素, 因为第一次选取之后一定会比较n−1n-1n−1次, 所以可得
Mn=∑j=1n(n−1+Mj−1+Mn−j)1n=n−1+1n∑k=1n−1Mk+1n∑m=n−11Mm=n−1+2n∑k=1n−1Mk\begin{split} 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{split} Mn​​=j=1∑n​(n−1+Mj−1​+Mn−j​)n1​=n−1+n1​k=1∑n−1​Mk​+n1​m=n−1∑1​Mm​=n−1+n2​k=1∑n−1​Mk​​
所以
nMn=n(n−1)+2∑k=1n−1MknM_n = n(n-1) + 2\sum_{k=1}^{n-1}M_k nMn​=n(n−1)+2k=1∑n−1​Mk​
易知
(n+1)Mn+1=n(n+1)+2∑k=1nMk(n+1)M_{n+1} = n(n+1) + 2\sum_{k=1}^{n}M_k (n+1)Mn+1​=n(n+1)+2k=1∑n​Mk​
所以
(n+1)Mn+1−nMn=n(n−1)=2n+2Mn(n+1)M_{n+1} - nM_n = n(n-1) = 2n+2M_n (n+1)Mn+1​−nMn​=n(n−1)=2n+2Mn​
即
(n+1)Mn+1=2n+(n+2)Mn(n+1)M_{n+1} = 2n+(n+2)M_n (n+1)Mn+1​=2n+(n+2)Mn​
所以
Mn+1=2nn+1+n+2n+1MnM_{n+1} = \frac{2n}{n+1} + \frac{n+2}{n+1}M_n Mn+1​=n+12n​+n+1n+2​Mn​

两边同除以(n+2)(n+2)(n+2), 有
Mn+1n+2=2n(n+1)(n+2)+Mnn+1\frac{M_{n+1}}{n+2} = \frac{2n}{(n+1)(n+2)} + \frac{M_n}{n+1} n+2Mn+1​​=(n+1)(n+2)2n​+n+1Mn​​
迭代这个过程, 有
Mn+1n+2=2n(n+1)(n+2)+(2(n−1)n(n+1)+Mn−1n)=⋯=2∑k=0n−1n−k(n+1−k)(n+2−k)(M1=0)\begin{split} \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{split} n+2Mn+1​​​=(n+1)(n+2)2n​+(n(n+1)2(n−1)​+nMn−1​​)=⋯=2k=0∑n−1​(n+1−k)(n+2−k)n−k​(M1​=0)​
所以
Mn+1=2(n+2)∑i=1ni(i+1)(i+2)(i=n−k)=2(n+2)[∑i=1n2i+2−∑i=1n1i+1]≈2(n+2)[∫3n+22xdx−∫2n+11xdx](步长为1的数值积分)≈2(n+2)ln(n+2)\begin{split} 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{split} Mn+1​​=2(n+2)i=1∑n​(i+1)(i+2)i​(i=n−k)=2(n+2)[i=1∑n​i+22​−i=1∑n​i+11​]≈2(n+2)[∫3n+2​x2​dx−∫2n+1​x1​dx](步长为1的数值积分)≈2(n+2)ln(n+2)​