对 x 1 , … , x n x_1,dots,x_n x1,…,xn进行快速排序 partition node: x [ k ] x[k] x[k]为随机划分元 x [ k ] x[k] x[k] 被选择的概率为 1 / n 1/n 1/n,令 C n C_n Cn 为规模为n的问题的比较次数(即 T ( n ) T(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 egin{align*} C_n&=(n-1)+frac{1}{n}sum_{k=1}^n(C_{k-1}+C_{n-k})\ &=(n-1)+frac{1}{n}sum_{k=1}^n C_{k-1}+frac{1}{n}sum_{k=1}^n C_{n-k}\ &=(n-1)+frac{1}{n}sum_{k=0}^{n-1} C_{k}+frac{1}{n}sum_{k=0}^{n-1} C_{k}\ &=(n-1)+frac{2}{n}sum_{k=0}^{n-1} C_{k} end{align*} Cn=(n−1)+n1k=1∑n(Ck−1+Cn−k)=(n−1)+n1k=1∑nCk−1+n1k=1∑nCn−k=(n−1)+n1k=0∑n−1Ck+n1k=0∑n−1Ck=(n−1)+n2k=0∑n−1Ck 因此 n C n = n ( n − 1 ) + 2 ∑ k = 0 n − 1 C k ① nC_n=n(n-1)+2sum_{k=0}^{n-1}C_kquad ① nCn=n(n−1)+2k=0∑n−1Ck① 用 n − 1 n-1 n−1 代入 n n n,得 ( n − 1 ) C n − 1 = ( n − 1 ) ( n − 2 ) + 2 ∑ k = 0 n − 2 C k ② (n-1)C_{n-1}=(n-1)(n-2)+2sum_{k=0}^{n-2}C_kquad② (n−1)Cn−1=(n−1)(n−2)+2k=0∑n−2Ck② ① − ② ①-② ①−② 得 n C n − ( n − 1 ) C n − 1 = 2 ( n − 1 ) + 2 C n − 1 ⇒ n C n = 2 ( n − 1 ) + ( n + 1 ) C n − 1 ③ ⇒ C n n + 1 = C n − 1 n + 2 ( n − 1 ) n ( n + 1 ) egin{align*} &nC_n-(n-1)C_{n-1}=2(n-1)+2C_{n-1}\ Rightarrow &nC_n=2(n-1)+(n+1)C_{n-1}quad ③\ Rightarrow &frac{C_n}{n+1}=frac{C_{n-1}}{n}+frac{2(n-1)}{n(n+1)} end{align*} ⇒⇒nCn−(n−1)Cn−1=2(n−1)+2Cn−1nCn=2(n−1)+(n+1)Cn−1③n+1Cn=nCn−1+n(n+1)2(n−1) 令 D n = C n n + 1 D_n=frac{C_n}{n+1} Dn=n+1Cn 得 D n = D n − 1 + 2 ( n − 1 ) n ( n + 1 ) ④ D_n=D_{n-1}+frac{2(n-1)}{n(n+1)}quad④ Dn=Dn−1+n(n+1)2(n−1)④ 因此 D n = 2 ∑ j = 1 n j − 1 j ( j + 1 ) = 2 ∑ j = 1 n 2 j + 1 − 2 ∑ j = 1 n 1 j = 4 ∑ j = 2 n + 1 1 j − 2 ∑ j = 1 n 1 j = 2 ∑ j = 1 n 1 j + 4 n + 1 − 4 = 2 H n − 4 n n + 1 ≈ 2 ln n + O ( 1 ) = 2 log 2 e log 2 n + O ( 1 ) ≈ 1.44 log 2 n egin{align*} D_n&=2sum_{j=1}^nfrac{j-1}{j(j+1)}\ &=2sum_{j=1}^nfrac{2}{j+1}-2sum_{j=1}^nfrac{1}{j}\ &=4sum_{j=2}^{n+1}frac{1}{j}-2sum_{j=1}^nfrac{1}{j}\ &=2sum_{j=1}^nfrac{1}{j}+frac{4}{n+1}-4\ &=2H_n-frac{4n}{n+1}\ &approx2ln n+O(1)\ &=frac{2}{log_2 e}log_2 n+O(1)\ &approx1.44log_2 n end{align*} Dn=2j=1∑nj(j+1)j−1=2j=1∑nj+12−2j=1∑nj1=4j=2∑n+1j1−2j=1∑nj1=2j=1∑nj1+n+14−4=2Hn−n+14n≈2lnn+O(1)=log2e2log2n+O(1)≈1.44log2n 因此 C n ≈ 1.44 n log 2 n = O ( n log n ) C_napprox1.44nlog_2 n=O(nlog n) Cn≈1.44nlog2n=O(nlogn)
快速排序平均时间复杂度分析 梳排序时间复杂度
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至lizi9903@foxmail.com举报，一经查实，本站将立刻删除。