algorithm - 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？

score 18 · Accepted Answer

对于n小于 0.49的值，n仅小于( log n) ^{2 ...}

所以一般来说（log n）²对于大n更好......

但是由于这些O (something) -notations 总是忽略常数因素，在你的情况下，可能无法确定哪种算法更好......

这是一个图表：

在此处输入图像描述

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

请注意， n的小值的差异如何并没有那么大，并且可能很容易被未包含在 Big-O 表示法中的常数因子相形见绌。

但是对于大n，( log n) ²胜出：

在此处输入图像描述

score 13 · Accepted Answer

对每个常数k渐近log(n)^k < n。

证明很简单，对等式两边都做log，你得到：

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

渐近地很容易看出，这是正确的。

语义注释：假设这里log(n)^k == log(n) * log(n) * ... * log(n) (k times)而不是log(log(log(...log(n)))..) (k times)有时也使用它。

score 3 · Accepted Answer

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

对数获胜。

score 0 · Accepted Answer

(logn)^2也是 < n.

举个例子：

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

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

即使您采用更大的 n 值，例如 100,000,000 ，那么

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

这远远小于n。

score 0 · Accepted Answer

0

(Log n)^2 更好，因为如果您通过 exp m 对 n 进行变量更改，则 m^2 优于 exp m

于 2012-12-04T19:48:43.720 回答

score -1 · Accepted Answer

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

从双方获取日志：

对数(n^2)=2对数(n)

对数(n(logn)^2)=对数(n)+2对数(对数(n))=对数(n)+2对数(对数(n))

lim n--> 无穷大 [(Log(n)+2log(Log(n)))/2log(n)/]=0.5（使用 l'Hôpital 规则）（http://en.wikipedia.org/wiki/ L'H%C3%B4pital's_rule)]

6 回答 6