我正在研究一个改进快速排序算法最坏情况时间复杂度的项目。我通过选择中间轴而不是最左边的选择来修改算法,并在一定次数的迭代后引入插入排序结果如下:
对于长度为5000到100000的未排序数据的输入:
在我修改的快速排序中进行的比较数量比在常规快速排序中进行的比较数量少得多。
对于所有长度的if数据,两者的运行时间均为零秒。
对于长度为5000到100000的已排序数据的输入:
在我的修改后的快速排序中进行的比较数量仍然比在常规快速排序中进行的比较数量少。
我修改的快速排序的运行时间比所有长度数据的常规快速排序的运行时间都要短。
现在我如何证明已经排序的数据的时间复杂度O(n^2)已经被改进了?我有以上所有的数据,但不知道如何从理论上证明它?没有直接的答案,但暗示是可以的。

最佳答案

在排序算法中演示算法改进的常用方法是使用代码来计算比较的次数,然后在几个不同的数据集上运行不同的算法,每个数据集具有不同的特性(随机、已排序、反向排序、主要排序等)。
这种分析的一个好模型是tim peter为他的Timsort算法写的文章:http://hg.python.org/cpython/file/2.7/Objects/listsort.txt

09-09 21:48
查看更多