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演示,请参阅:

O(n)与O(nlogn)

为了获得更好的效果,可以尝试在标准的不相交集数据结构上绘制n个操作所花费的时间。 它已被certificate是渐近的nα( n ),其中α( n )是阿克曼函数的倒数(尽pipe你通常的algorithm教科书可能只会显示n log log n或可能n log * n的界限)。 对于input大小可能遇到的任何types的数字,α( n )≤5(实际上log * n≤5),尽pipe它渐近地逼近无穷大。

我想你可以从中学习到,虽然渐近复杂性是一个非常有用的思考algorithm的工具,但与实际效率并不是一回事。

  1. 通常O(n * log(n))algorithm具有2基对数实现。
  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))这么好!