视频建设网站,合肥互联网公司,Wordpress教程推荐,有几家做网站的公司好条件期望例题----快排算法的分析
快速排序算法的递归定义如下: 有n个数(n≥2n\geq 2n≥2), 一开始随机选取一个数xix_ixi, 并将xix_ixi和其他n-1个数进行比较, 记SiS_iSi为比xix_ixi小的元素构成的集合, Siˉ\bar{S_i}Siˉ为比xix_ixi大的元素构成的集合, 然后分…条件期望例题----快排算法的分析
快速排序算法的递归定义如下: 有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个不同元素的集合中, 实行快速排序算法所需要的比较次数的均值, 易知M0M10,M20.5M_0 M_1 0, M_2 0.5M0M10,M20.5. 易知 Mn∑j1nE[比较次数∣初始随机取的元素为集合中的第j个值]1nM_n \sum_{j1}^nE[比较次数|初始随机取的元素为集合中的第j个值]\frac{1}{n} Mnj1∑nE[比较次数∣初始随机取的元素为集合中的第j个值]n1 如果初始选的值是所有元素中第jjj小的, 则对应的SSS集合就有j−1j-1j−1个元素, Sˉ\bar{S}Sˉ就有n-j个元素, 因为第一次选取之后一定会比较n−1n-1n−1次, 所以可得 Mn∑j1n(n−1Mj−1Mn−j)1nn−11n∑k1n−1Mk1n∑mn−11Mmn−12n∑k1n−1Mk\begin{split} M_n \sum_{j1}^n(n-1 M_{j-1} M_{n-j})\frac{1}{n} \\ n-1 \frac{1}{n}\sum_{k1}^{n-1}M_k \frac{1}{n}\sum_{mn-1}^{1}M_m \\ n-1 \frac{2}{n}\sum_{k1}^{n-1}M_k \end{split} Mnj1∑n(n−1Mj−1Mn−j)n1n−1n1k1∑n−1Mkn1mn−1∑1Mmn−1n2k1∑n−1Mk 所以 nMnn(n−1)2∑k1n−1MknM_n n(n-1) 2\sum_{k1}^{n-1}M_k nMnn(n−1)2k1∑n−1Mk 易知 (n1)Mn1n(n1)2∑k1nMk(n1)M_{n1} n(n1) 2\sum_{k1}^{n}M_k (n1)Mn1n(n1)2k1∑nMk 所以 (n1)Mn1−nMnn(n−1)2n2Mn(n1)M_{n1} - nM_n n(n-1) 2n2M_n (n1)Mn1−nMnn(n−1)2n2Mn 即 (n1)Mn12n(n2)Mn(n1)M_{n1} 2n(n2)M_n (n1)Mn12n(n2)Mn 所以 Mn12nn1n2n1MnM_{n1} \frac{2n}{n1} \frac{n2}{n1}M_n Mn1n12nn1n2Mn
两边同除以(n2)(n2)(n2), 有 Mn1n22n(n1)(n2)Mnn1\frac{M_{n1}}{n2} \frac{2n}{(n1)(n2)} \frac{M_n}{n1} n2Mn1(n1)(n2)2nn1Mn 迭代这个过程, 有 Mn1n22n(n1)(n2)(2(n−1)n(n1)Mn−1n)⋯2∑k0n−1n−k(n1−k)(n2−k)(M10)\begin{split} \frac{M_{n1}}{n2} \frac{2n}{(n1)(n2)} \left(\frac{2(n-1)}{n(n1)} \frac{M_{n-1}}{n} \right) \\ \cdots \\ 2\sum_{k0}^{n-1}\frac{n-k}{(n1-k)(n2-k)} \\ (M_1 0) \end{split} n2Mn1(n1)(n2)2n(n(n1)2(n−1)nMn−1)⋯2k0∑n−1(n1−k)(n2−k)n−k(M10) 所以 Mn12(n2)∑i1ni(i1)(i2)(in−k)2(n2)[∑i1n2i2−∑i1n1i1]≈2(n2)[∫3n22xdx−∫2n11xdx](步长为1的数值积分)≈2(n2)ln(n2)\begin{split} M_{n1} 2(n2)\sum_{i1}^{n}\frac{i}{(i1)(i2)} \\ (i n-k) \\ 2(n2)\left[\sum_{i1}^{n}\frac{2}{i2} - \sum_{i1}^{n}\frac{1}{i1} \right] \\ \approx 2(n2)\left[ \int_3^{n2}\frac{2}{x}dx - \int_2^{n1}\frac{1}{x}dx\right] \\ (步长为1的数值积分) \\ \approx 2(n2)ln(n2) \end{split} Mn12(n2)i1∑n(i1)(i2)i(in−k)2(n2)[i1∑ni22−i1∑ni11]≈2(n2)[∫3n2x2dx−∫2n1x1dx](步长为1的数值积分)≈2(n2)ln(n2)
