[关闭]
@Pigmon 2017-10-12T05:51:02.000000Z 字数 1479 阅读 160

算法作业__3_袁胜_2016M8009073008

Python


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

不失一般性,设待排序数组长度 ,令所求平均元素移动次数为

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

合并阶段:

...

总移动次数为:

展开为:

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

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

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


快排序元素移动次数分析

令待排序数组长度为 ,令所求平均元素移动次数为

分组次数为

在任意一个长度为 的分组中,平均情况下移动元素次数为,即一次划分后,所有分组的平均移动元素个数的和为

即快排序平均情况下元素移动次数的数量级为

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注