哪个更好：O（n log n）或O（n ^ 2） [英] Which is better: O(n log n) or O(n^2)

问题描述

好的，我有这个项目要做，但我只是不理解。问题是，我有2种算法。 O（n ^ 2）和 O（n * log ₂ n）。

无论如何，我在项目信息中发现，如果 n< 100 ，则 O（n ^ 2）效率更高，但是如果 n> = 100 ，则 O（n * log ₂ n）效率更高。我想用数字和单词或画一张照片来举例说明。但是，问题是，我不明白这一点，也不知道如何证明这一点。

这里有人可以帮助我了解其工作原理吗？ p>

提前加油！

编辑：谢谢大家的答复。

解决方案

只需问 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 n log（n）较小（更好）。 c $ c>足够高。 / p>

Okay so I have this project I have to do, but I just don't understand it. The thing is, I have 2 algorithms. O(n^2) and O(n*log₂n).

Anyway, I find out in the project info that if n<100, then O(n^2) is more efficient, but if n>=100, then O(n*log₂n) is more efficient. I'm suppose to demonstrate with an example using numbers and words or drawing a photo. But the thing is, I don't understand this and I don't know how to demonstrate this.

Anyone here that can help me understand how this works?

Cheers in advance!

EDIT: Thanks all for the replies.

解决方案

Just ask wolframalpha if you have doubts.

In this case, it says

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

Or you can also calculate the limit yourself:

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

That means n^2 grows faster, so n log(n) is smaller (better), when n is high enough.

这篇关于哪个更好：O（n log n）或O（n ^ 2）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！