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

Question

据我所知，我的大学已经证明，对随机数据进行排序的基于比较的算法的下界是Ω（nlogn）。我也知道Heapsort和Quicksort的平均情况是O（nlgn）。

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

我使用了发布在Roseta Code的算法：quicksort和heapsort。当我试图绘制时间每一个排序随机数据，多达1万个号码需要，我似乎是线性以下图表：

您还可以找到结果我从运行从here heapsort得到。 此外，您还可以找到我从运行快速排序得到了here

然而调查结果，我得到为O（n^2）的时间复杂度运行冒泡时，如下面的图中显示：

为什么这是？我可能会在这里错过什么？

Answer 1

的差别只是太小，用肉眼看，在这个规模：

使用您的堆排序结果（达到1000000项600毫秒），这里是一个O(n)功能（绿色）和O(n log n)功能（红） ： （从http://fooplot.com/plot/gnbb0vdgno）

在这张照片的两个功能是：

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

（请注意，这些功能有很大的不同恒定的缩放因素，但当然，这些并不在大O符号无所谓。）

但是仅仅是因为他们很难在图表中看到，并不意味着它们无法区分。

正如评论中所提到的，您的主要选项是较大的数据集或较慢的比较函数。大多数排序算法将允许您指定一个比较函数，在正常情况下，它不应该改变O（）时间复杂度。 （但要小心非传递式比较函数）

如果这是不可能的，并且您只是想将算法作为黑盒函数，那么您可以简单地重复实验并对结果进行平均，直到噪声足够低以区分这两条曲线。

能得到相应的“理想” N日志N曲线与平均数据比较，你需要解决的方程y = a*x * log(x); y=MAXIMUM_TIME; x=MAXIMUM_INPUT_LENGTH;，例如用Wolfram Alpha

---

很重要的一点这里要说的是，即使这些曲线看起来相似，但这并不意味着假设的线性排序算法的运行时间对于少于一百万个条目是不值得的。如果你设法拿出一个线性与作为n为log N算法相同常数因子排序算法，该曲线是这样的：