作业帮 > 数学 > 作业

数据结构排序算法中元素的平均移动次数如何求

来源:学生作业帮 编辑:搜搜考试网作业帮 分类:数学作业 时间:2024/04/29 10:50:18
数据结构排序算法中元素的平均移动次数如何求
比如快速排序和归并排序(二路)算法的平均移动次数
数据结构排序算法中元素的平均移动次数如何求
设X1,X2,……,Xn为有序的n个数,将其随机打乱,设其位置分别为P1,P2,……,Pk.算出每个Xk的移动次数Mk,然后累加后,求期望.
这是最基本的办法,通常也最最复杂.具体到特定的排序算法,可以考虑根据其特定简化计算,就会比较简单了