C语言 选择排列和归并排列,对于n个数处理的比较次数,求计算量的表达式...
发布网友
发布时间：2022-05-23 02:29
共1个回答
热心网友
时间：2022-05-22 02:47
无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数为：
n(n-1)/2=0(n2)
记录的移动次数
当初始文件为正序时，移动次数为0
文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。
总计算量为(n+3)(n-1)
归并排序
对长度为n的文件，需进行lgn趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
