算法作业__3_袁胜_2016M8009073008

Python

---

归并排序元素移动次数分析

不失一般性，设待排序数组长度 $n=2^k$，令所求平均元素移动次数为 $A(n)$。

归并排序的分割阶段不需要移动元素。

合并阶段：

• 第一次合并成 $\frac{n}{2}$ 个长度为$2$的分组，不需要移动元素；

• 第二次将长度为 $2$ 的所有分组合并为$\frac{n}{4}$个长度为$4$的分组时，每个$2$分组需要移动$1$次元素，即总共移动$\frac{n}{2}$次。

• 第三次将长度为 $4$ 的所有分组合并成为$\frac{n}{8}$个长度为$8$的分组时，每个$4$分组需要移动3次元素，即总共移动$\frac{n}{4}\times3$次。

...

• 第 $k-1$次，将$\frac{n}{2^{k-1}}$个，即$2$个长度为$2^{k-1}$，即长度为$\frac{n}{2}$的分组合并为长度为 $n$ 的已排序数组，需要移动$\frac{n}{2^{k-1}}\times(2^{k-1}-1)$次。

$\therefore$ 总移动次数为：

$$A(n) = \sum_{k=1}^{\log_2^n-1} \frac{n}{2^k}\times(2^k-1)$$

展开为：

$A(n)=\frac{n}{2}+\frac{n}{4}\times3+\frac{n}{8}\times7+ ... +\frac{n}{2^{k-1}}\times(2^{k-1}-1)$

$=n\times[\frac{1}{2}\times(2-1)+\frac{1}{2^2}\times(2^2-1)+\frac{1}{2^3}\times(2^3-1)+...+\frac{1}{2^{k-1}}\times(2^{k-1}-1)]$

$=n\times(1-\frac{1}{2}+1-\frac{1}{2^2}+1-\frac{1}{2^3}+...+1-\frac{1}{2^{k-1}})$

$=n\times[(k-1)-(\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+...+\frac{1}{2^{k-1}})]$

$=n\times[(k-1)-\frac{1}{2}(1+\frac{1}{2}+\frac{1}{2^2}+...+\frac{1}{2^{k-2}})]$

$=n\times[(k-1)-1+\frac{1}{2^{k-1}}]$

$=n(k-2+\frac{1}{2^{k-1}})$

$\because n=2^k$

$\therefore k=\log_2^n, \frac{1}{2^{k-1}}=\frac{2}{n}$

$A(n)=n\times(\log_2^n-2+\frac{2}{n})$

$=n\times\log_2^n-2n+2$

$=n\times(\log_2^n-2)+2$

$\therefore 归并排序移动次数的数量级为 O(nlgn)$

$\because$ 归并排序每次合并后的分组是有序的。

$\therefore$ 归并排序的移动次数是根据待排序数组长度的固定值。

$\therefore$ 该结果即为归并排序元素移动次数的平均情况下的数量级。

---

快排序元素移动次数分析

令待排序数组长度为 $n$，令所求平均元素移动次数为 $A(n)$

分组次数为$\log_2^n$。

在任意一个长度为 $l$ 的分组中，平均情况下移动元素次数为$\frac{l}{2}$，即一次划分后，所有分组的平均移动元素个数的和为$\frac{n}{2}$。

$$\therefore A(n)=\log_2^n\times\frac{n}{2}=\frac{n}{2}\log_2^n$$

即快排序平均情况下元素移动次数的数量级为 $O(nlgn)$