所以我想我会因为问这样一个微不足道的问题而被埋葬，但我对某事有点困惑。
我已经在 Java 和 C 中实现了快速排序，我正在做一些基本的比较。该图显示为两条直线，在 100,000 个随机整数上，C 比 Java 快 4 毫秒。
我的测试代码可以在这里找到；
android-benchmarks
我不确定 (n log n) 线会是什么样子，但我认为它不会是直的。我只是想检查一下这是否是预期的结果，并且我不应该尝试在我的代码中找到错误。
我将公式粘贴到 excel 中，对于基数 10，它似乎是一条开始时有扭结的直线。这是因为 log(n) 和 log(n+1) 之间的差异线性增加吗？
谢谢，
加夫
最佳答案
把图放大，你会发现 O(n logn) 不是一条直线。但是，是的，它非常接近线性行为。要了解原因，只需取几个非常大的数字的对数即可。
例如(基数为 10):
log(1000000) = 6
log(1000000000) = 9
…
因此，要对 1,000,000 个数字进行排序，O(n logn) 排序会增加一个微不足道的因子 6(或者只是多一点，因为大多数排序算法将取决于以 2 为底的对数)。不是很多。
事实上，这个对数因子非常小，以至于对于大多数数量级，已建立的 O(n logn) 算法优于线性时间算法。一个突出的例子是后缀数组数据结构的创建。
一个简单的案例最近让我咬了 when I tried to improve a quicksort sorting of short strings by employing radix sort 。事实证明，对于短字符串，这种(线性时间)基数排序比快速排序快，但是对于仍然相对较短的字符串有一个临界点，因为基数排序在很大程度上取决于您排序的字符串的长度。
关于language-agnostic - O(N log N) 复杂度 - 类似于线性？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/962545/