据我从我的大学学到的，证明了对随机数据进行排序的基于比较的算法的下界是 Ω(nlogn)。我也知道 Heapsort 和 Quicksort 的平均情况是 O(nlgn)。
因此，我尝试绘制这些算法对一组随机数据进行排序所需的时间。
我使用了 Roseta Code 上发布的算法:quicksort和 heapsort .当我试图绘制每个人对随机数据进行排序所需的时间时，对于多达 100 万个数字，我得到了以下看起来是线性的图表:
您还可以找到我从 here 运行堆排序得到的结果. 此外，您还可以找到我从 here 运行快速排序得到的结果。
但是，在运行冒泡排序时，我确实得到了 O(n^2) 的时间复杂度，如下图所示:
这是为什么？我可能在这里遗漏了什么？
最佳答案
在这个比例下，差异太小了，用肉眼是看不出来的:
使用您的 HeapSort 结果(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)red
(请注意，这些函数具有截然不同的常数比例因子，但当然这些在 Big-O 表示法中无关紧要。)
然而，仅仅因为它们很难在图表中看到，并不意味着它们无法区分。
如评论中所述，您的主要选择是更大的数据集或更慢的比较函数。大多数排序算法将允许您指定一个比较函数，在正常情况下，它不应该改变 O() 时间复杂度。 (尽管要注意非传递比较函数)
如果那是不可能的，并且您只想将算法作为黑盒进行线程化，则可以简单地重复实验并对结果进行平均，直到噪声低到足以区分这两条曲线为止。
要获得适当的“理想”n log n 曲线以与平均数据进行比较，您需要求解方程 y = a*x * log(x); y=最大时间； x=MAXIMUM_INPUT_LENGTH;，例如 Wolfram Alpha
这里的一个重点是，尽管这些曲线看起来很相似，但这并不意味着假设的线性排序算法的运行时间对于少于一百万个条目来说不值得。如果您设法想出一个与 n log n 算法具有相同常数因子的线性排序算法，则曲线将如下所示:
关于algorithm - 运行合并排序和快速排序时的线性时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24586134/