所以我想我会因为问这么一个微不足道的问题而被埋葬，但我对某些事情有点困惑。
我已经在 Java 和 C 中实现了快速排序，并且正在做一些基本的比较。该图显示为两条直线，在超过 100,000 个随机整数时，C 比 Java 快 4 毫秒。
我的测试代码可以在这里找到；
我不确定 (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) 算法优于线性时间算法。一个突出的例子是创建后缀数组数据结构。
最近，当我尝试通过使用 radix sort 来改进短字符串的快速排序时，一个简单的案例让我感到困扰。事实证明，对于短字符串，这种（线性时间）基数排序比快速排序更快，但是对于仍然相对较短的字符串存在一个临界点，因为基数排序关键取决于您排序的字符串的长度。
仅供参考，快速排序实际上是 O(n^2)，但平均情况为 O(nlogn)
仅供参考，O（n）和O（nlogn）之间存在很大差异。这就是为什么它对于任何常数都不受 O(n) 的限制。
有关图形演示，请参见：
为了以类似的方式获得更多乐趣，请尝试在标准不相交集数据结构上绘制n 个操作所花费的时间。它已被证明是渐近的n α( n ) 其中 α( n ) 是Ackermann 函数的倒数（尽管您通常的算法教科书可能只会显示n log log n或可能n log* n的界限）。对于您可能会遇到的任何类型的数字作为输入大小，α( n ) ≤ 5（实际上是 log* n ≤ 5），尽管它确实渐近无穷大。
我想你可以从中学到的是，虽然渐近复杂度是思考算法的一个非常有用的工具，但它与实际效率并不完全相同。
因此，O(n*log(n)) 仅对于少量数据类似于线性。
提示：不要忘记快速排序在随机数据上的表现非常好，而且它不是 O(n*log(n)) 算法。
如果选择正确的轴，任何数据都可以绘制在一条线上:-)
维基百科说 Big-O 是最坏的情况（即 f(x) 是 O(N) 意味着 f(x) 以 N“为界”）https://en.wikipedia.org/wiki/Big_O_notation
这是一组很好的图表，描述了各种常用函数之间的差异：http: //science.slc.edu/~jmarshall/courses/2002/spring/cs50/BigO/
log(x) 的导数是 1/x。这是随着 x 增加 log(x) 增加的速度。它不是线性的，尽管它可能看起来像一条直线，因为它弯曲得太慢了。当考虑 O(log(n)) 时，我认为它是 O(N^0+)，即 N 的最小幂，它不是一个常数，因为 N 的任何正常数幂最终都会超过它。这不是 100% 准确的，所以如果你这样解释，教授会生你的气的。
两个不同碱基的对数之间的差异是一个常数乘数。查找在两个基数之间转换日志的公式：（在此处的“基数更改”下：https ://en.wikipedia.org/wiki/Logarithm ）诀窍是将 k 和 b 视为常量。
在实践中，您绘制的任何数据通常都会出现一些问题。程序之外的东西会有所不同（在程序之前交换到 cpu 中的东西、缓存未命中等）。需要多次运行才能获得可靠的数据。常量是将 Big O 表示法应用于实际运行时的最大敌人。对于足够小的 N，具有高常数的 O(N) 算法可能比 O(N^2) 算法慢。
log(N) （非常）大致是 N 中的位数。因此，在大多数情况下，log(n) 和 log(n+1) 之间几乎没有区别
尝试在其顶部绘制一条实际的线性线，您会看到小幅增加。请注意，50,0000 处的 Y 值小于 100,000 处的 1/2 Y 值。
它在那里，但它很小。这就是为什么 O(nlog(n)) 这么好！