O（N log N）复杂性 – 类似于线性？
所以我想我会因为问这样一个微不足道的问题而被埋葬，但是我有点困惑。
我已经在Java和C中实现了quicksort，我正在做一些基本的比较。 该graphics是以两条直线出现的，其中C是比Java对应的超过100,000个随机整数更快的4ms。
我的testing代码可以在这里find;
Android的基准
我不确定（n log n）行会是什么样子，但我不认为它会是直的。 我只是想检查这是预期的结果，我不应该试图find我的代码中的错误。
我把这个公式固定在excel中，而基数10似乎是一开始就有一个扭曲的直线。 这是因为log（n）和log（n + 1）之间的差异是线性增加的吗？
谢谢，
GAV
使graphics变大，你会看到O（n logn）不是一条直线。 但是，是的，线性行为非常接近。 为了明白为什么，只取一些非常大的数字的对数。
例如（基数10）：
log(1000000) = 6 log(1000000000) = 9 … 所以，要sorting1,000,000个数字，O（n logn）sorting会添加一个可疑因子6（或者多一点，因为大多数sortingalgorithm将取决于基数2的对数）。 不是一个可怕的很多。
事实上，这个对数因子是非常小的，对于大多数的数量级，build立的O（n logn）algorithm的性能优于线性时间algorithm。 一个突出的例子是创build一个后缀数组数据结构。
一个简单的例子最近咬了我， 当我试图通过采用基数sorting来改善短串的sorting 。 原来，对于短string来说，这个（线性时间）基数sorting比快速sorting要快，但是对于相对较短的string，却有一个临界点，因为基数的sorting关键取决于您sorting的string的长度。
仅供参考，quicksort实际上是O（n ^ 2），但平均情况下O（nlogn）
仅供参考，O（n）和O（nlogn）之间有很大的区别。 这就是为什么它不受O（n）限制的任何常量。
有关graphics演示，请参阅：
为了获得更好的效果，可以尝试在标准的不相交集数据结构上绘制n个操作所花费的时间。 它已被certificate是渐近的nα（ n ），其中α（ n ）是阿克曼函数的倒数（尽pipe你通常的algorithm教科书可能只会显示n log log n或可能n log * n的界限）。 对于input大小可能遇到的任何types的数字，α（ n ）≤5（实际上log * n≤5），尽pipe它渐近地逼近无穷大。
我想你可以从中学习到，虽然渐近复杂性是一个非常有用的思考algorithm的工具，但与实际效率并不是一回事。
- 通常O（n * log（n））algorithm具有2基对数实现。
- 对于n = 1024，log（1024）= 10，所以n * log（n）= 1024 * 10 = 10240的计算，增加一个数量级。
所以，O（n * log（n））只对less量数据类似于线性。
提示：不要忘记，快速sorting在随机数据上的performance非常好，而且它不是O（n * log（n））algorithm。
如果轴select正确，任何数据都可以绘制在一条线上:-)
维基百科说，大O是最糟糕的情况（即f（x）是O（N）意思是f（x）是“受限于”N） https://en.wikipedia.org/wiki/Big_O_notation
下面是一组描述各种常见function之间差异的图表： http : //science.slc.edu/~jmarshall/courses/2002/spring/cs50/BigO/
log（x）的导数是1 / x。 这是log（x）随着x的增加而增加的速度。 它不是线性的，虽然它看起来像一条直线，因为它弯曲得很慢。 当考虑到O（log（n））时，我认为它是O（N ^ 0 +），也就是N的最小幂不是一个常数，因为N的正的常数幂最终会超过它。 这不是100％准确的，所以如果你这样解释，教授们会生气的。
两个不同基地的日志之间的差异是一个不变的乘数。 查找两个基地之间的转换公式：（在“基地的变化”这里： https ： //en.wikipedia.org/wiki/Logarithm ）诀窍是把k和b作为常量。
在实践中，你所绘制的任何数据通常都会出现一些呃逆。 在你的程序之外的东西将会有所不同（比如在程序之前换入CPU，caching未命中等等）。 需要多次运行才能获得可靠的数据。 常量是尝试将Big O符号应用于实际运行时的最大敌人。 具有高常数的O（N）algorithm对于足够小的N可比O（N ^ 2）algorithm慢。
log（N）大体上是N中的位数。因此，log（n）和log（n + 1）之间几乎没有差别，
尝试绘制一个实际的线性线上，你会看到小的增加。 请注意，50,0000处的Y值小于100,000处的1/2 Y值。
它在那里，但它很小。 这就是为什么O（nlog（n））这么好！
