O(n^2) 和 O(n(logn)^2)的比较

Question

时间复杂度是 O(n^2) 还是 O (n(logn)^2) 更好？

我知道当我们简化它时，它变成了什么。

O(n) vs O((logn)^2)

如果 logn < n，那么 logn^2 又是怎样的呢？

- Chin

Answer 1

n只有在小于0.49的n值下才小于(log n)²...

所以一般情况下，对于较大的n，(log n)²更好...

但是由于这些O(something)表示法总是省略常数因子，在您的情况下可能无法确定哪个算法更好...

下面是一张图：

(蓝线是n，绿线是(log n)²)

请注意，对于小的n 值，差异并不是很大，很容易被未包括在Big-O标记中的常数因子所掩盖。

但对于较大的n 值，(log n)²胜出：

- Markus A.

---

请注意，绿线在n取非常小的值时会急速上升到无限大。渐近分析并不关注于某个量是否趋向于无限大，而是关注它趋向于无限大的速度有多快。log(n)^2也会趋向于无限大。 - phant0m

@phant0m 我想指出的是，对于小的n值，(log n)^2也会趋向于无穷大，而不仅仅是大的n值。但这更多是一个纯数学观察，因为通常情况下n不会小于1...我会删除这行。它并没有真正添加任何有用的信息... - Markus A.

Answer 2

对于每个常数 k，渐近地有log(n)^k < n。

证明很简单，两侧取对数，即可得到：

log(log(n))*k < log(n)

很容易看出，在渐近意义下，这是正确的。

---

语义说明：在此假设 log(n)^k == log(n) * log(n) * ... * log(n) (重复k次) 而不是有时也被使用的 log(log(log(...log(n)))..) (重复k次)。

- amit

Answer 3

O(n^2) vs. O(n*log(n)^2)
<=> O(n) vs. O(log(n)^2) (divide by n)
<=> O(sqrt(n)) vs. O(log(n)) (square root)
<=> polynomial vs. logarithmic

对数胜出。

- Timothy Shields

Answer 4

(logn)^2 也小于 n。

举个例子：

 n = 5
 log n = 0.6989....
 (log n)^ 2 = 0.4885..

你可以看到，(long n)^2 被进一步缩小。

即使你取任何更大的值，例如 100,000,000，那么

   log n = 9
   (log n)^ 2 = 81

这远远小于n。

- Yogendra Singh

---

log(100) < log(100)^2（假设^2表示log(100)*log(100)），n==5是一个不好的例子。 - amit

试着用一百万进行计算。log n = 13.8155...，它的平方是190.8683...。请记住，O（N的某个函数）处理大的N值。 - cHao

@amit，我在例子中使用了更大的数字。我已经更新了答案。 - Yogendra Singh

@cHao 我已经选了一个更大的数字作为示例，我认为这已经足够好了。 - Yogendra Singh

Answer 5

(Log n)^2更好，因为如果你通过变量替换n为exp m，那么m^2比exp m更好。

- Nahuel Fouilleul

Answer 6

对于大的n，O(n(logn)^2)更好（更快）！

两边取对数：

Log(n^2)=2log(n)

Log(n(logn)^2)=Log(n)+2log(Log(n))=Log(n)+2log(Log(n))

当n趋近于无穷大时，lim [(Log(n)+2log(Log(n)))/2log(n)/]=0.5（使用l'Hôpital法则）（http://en.wikipedia.org/wiki/L'H%C3%B4pital's_rule）

- Reza

---

我认为OP想要的是(log(n))^2而不是log(n^2)。 - amit

你是对的：log(n(log(n)^2)=log(n)+log(log(n)^2)=log(n)+2(log(log(n)) - Reza