哪个更好:O(n log n)或O(n ^ 2)

Question

好的,所以我有这个项目我必须做,但我只是不明白.问题是,我有2个算法.O(n ^ 2)和O(n*log ₂ n).

无论如何,我在项目信息中发现,如果n <100,则O(n ^ 2)更有效,但如果n> = 100,则O(n*log ₂ n)更有效.我想用一个例子来演示使用数字和单词或绘制照片.但问题是,我不明白这一点,我不知道如何证明这一点.

这里的任何人都可以帮我理解这是如何工作的？

提前干杯!

编辑:谢谢大家的回复.

Answer 1

好问题.实际上,我总是展示这3张照片:

n = [0; 10]

n = [0; 100]

n = [0; 1000]

所以,O(N*log(N))远胜于O(N^2).它是更接近O(N)比O(N^2).

但是你的O(N^2)算法N < 100在现实生活中更快.有很多原因可以让它更快.可能是由于更好的内存分配或其他"非算法"效果.也许O(N*log(N))算法需要一些数据准备阶段或O(N^2)迭代更短.无论如何,Big-O表示法仅适用于足够大的Ns.

如果你想证明为什么一个算法对于小N更快,你可以测量1次迭代的执行时间和两种算法的恒定开销,然后用它们来纠正理论图:

例

或者只是测量两种算法的执行时间以用于不同的Ns和绘制经验数据.

Answer 2

如果你有疑问,请问wolframalpha.

在这种情况下,它说

     n log(n)
lim --------- = 0
       n^2

或者您也可以自己计算限额:

     n log(n)        log(n)   (Hôpital)       1/n          1
lim --------- = lim --------      =     lim ------- = lim --- = 0
       n^2             n                       1           n

这意味着n^2增长得更快,因此n log(n)更小(更好),当n足够高时.

Answer 3

Big-O表示法是渐近复杂性的表示法.这意味着它在N任意大时计算复杂度.

对于小Ns,还有很多其他因素.算法可能有O(n ^ 2)循环迭代,但每次迭代都很短,而另一种算法有O(n)次迭代,迭代次数很长.对于大Ns,线性算法将更快.对于小Ns,二次算法将更快.

因此,对于小N,只需测量两个,看看哪个更快.无需进入渐近复杂性.

顺便说一下,不要写日志的基础.Big-O表示法忽略常量 - O(17*N)与O(N)相同.由于log ₂ N是公正的ln N / ln 2,因此对数的基础只是另一个常数而被忽略.

Answer 4

我们来比较一下,

一方面我们有:

n^2 = n * n

另一方面,我们有:

nlogn = n * log(n)

把它们放在一边:

n * n    versus    n * log(n)

让我们除以n哪个是一个常用术语,得到:

n    versus    log(n)

让我们比较一下价值:

n = 10           log(n) ~ 2.3
n = 100          log(n) ~ 4.6
n = 1,000        log(n) ~ 6.9
n = 10,000       log(n) ~ 9.21
n = 100,000      log(n) ~ 11.5
n = 1,000,000    log(n) ~ 13.8

所以我们有:

n >> log(n) for n > 1

n^2 >> n log(n) for n > 1