为O（n ^ 2）与O（N（logn）时间^ 2）(O(n^2) vs O (n(logn)^2))

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

我知道，当我们把它简化，它变得

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

和logn < n ，但对于logn^2 ？

Answer 1:

n为只比（log n）的²小于0.49的n个值少...

所以一般（log n）的²是大的n更好的... ...

但是，由于这些O（东西）-notations总是忽略常数因子，在你的情况下，它可能无法肯定地说哪种算法更好...

这里有一个图表：

（蓝线是n和绿线（log n）的^2）

请注意，对于n值很小的差别是多么的不那么大，可能很容易被不包括在大O符号常量因素相形见绌。

但对于大的n（log n）的^2个胜手了：

Answer 2:

对于每个恒定k渐近log(n)^k < n

证明很简单，不要登录等式的两边，你会得到：

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

这是很容易看到，渐进，这是正确的。

---

语义注：这里假设log(n)^k == log(n) * log(n) * ... * log(n) (k times)和NOT log(log(log(...log(n)))..) (k times) ，因为它有时也被使用。

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

对数胜。

Answer 4:

（log n）的^ 2更好，因为如果通过EXP m执行一个变量的变化N，则m ^ 2比EXP米更好

Answer 5:

(logn)^2也< n 。

举一个例子：

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

你可以看到，（长N）^ 2进一步降低。

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

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

这远远小于n 。

Answer 6:

O（N（LOGN）^ 2）是大的n更好（快）！

采取日志双方：

的log（n ^ 2）= 2log（n）的

的log（n（logn）时间^ 2）=的log（n）+ 2log（的log（n））=的log（n）+ 2log（日志（n））的

LIM N - >无穷[（日志（N）+ 2log（日志（N）））/ 2log（N）/] = 0.5（使用洛必达法则）（http://en.wikipedia.org/wiki/ L'H％C3％B4pital's_rule）]

文章来源: O(n^2) vs O (n(logn)^2)