运行合并排序和快速排序时的线性时间

Question

据我所知,从我的大学中可以看出,对随机数据进行排序的基于比较的算法的下限是Ω(nlogn).我也知道Heapsort和Quicksort的平均情况是O(nlgn).

因此,我试图绘制这些算法对一组随机数据进行排序所需的时间.

我用的是张贴在Roseta代码的算法:快速排序和堆排序.当我试图绘制每个人需要对随机数据进行排序的时间时,对于高达1百万的数字,我得到了以下似乎是线性的图表:

你也可以从这里找到我从运行heapsort得到的结果.此外,您还可以从此处找到从运行quicksort获得的结果

但是,运行bubblesort时,我确实得到O(n ^ 2)时间复杂度,如下图所示:

为什么是这样？我可能在这里失踪了什么？

Answer 1

差异太小,无法用肉眼看到这种规模:

使用HeapSort结果(1000000条目为600ms),这是一个O(n)函数(绿色)和一个O(n log n)函数(红色): (来自http://fooplot.com/plot/gnbb0vdgno)

这张图中的两个功能是:

• y = 600/1000000 * x ^绿色
• y = 1/(10000 log(10)) * x*log(x) ^红色

(请注意,这些函数具有截然不同的常量缩放因子,但当然这些在Big-O表示法中无关紧要.)

然而,仅仅因为它们很难在图表中看到,并不意味着它们无法区分.

正如评论中所提到的,您的主要选项是更大的数据集或更慢的比较函数.大多数排序算法允许您指定比较函数,在正常情况下,不应该更改O()时间复杂度.(谨防非传递性比较功能)

如果这是不可能的,并且您只想将算法作为黑盒子进行处理,则可以简单地重复实验并对结果取平均值,直到噪声足够低以区分这两条曲线.

要获得适当的"理想"n log n曲线以与平均数据进行比较,您需要求解方程y = a*x * log(x); y=MAXIMUM_TIME; x=MAXIMUM_INPUT_LENGTH;,例如使用Wolfram Alpha

这里的一个重点是,即使这些曲线看起来相似,但这并不意味着假设的线性排序算法的运行时间对于少于一百万个条目是不值得的.如果您设法提出了与n log n算法具有相同常数因子的线性排序算法,则曲线将如下所示: