是时间复杂度O(n^2)还是O (n(logn)^2)更好？
我知道当我们简化它时，它变成
O(n) vs O((logn)^2)
和logn< n，但是呢logn^2？
问问题
55279 次
6 回答
18
对于n小于 0.49的值，n仅小于( log n) 2 ...
所以一般来说（log n）2对于大n更好......
但是由于这些O (something) -notations 总是忽略常数因素，在你的情况下，可能无法确定哪种算法更好......
这是一个图表：
（蓝线是n，绿线是( log n) 2）
请注意， n的小值的差异如何并没有那么大，并且可能很容易被未包含在 Big-O 表示法中的常数因子相形见绌。
但是对于大n，( log n) 2胜出：
于 2012-12-04T19:48:03.780 回答
13
对每个常数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)有时也使用它。
于 2012-12-04T19:46:08.493 回答
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
对数获胜。
于 2012-12-04T19:54:36.470 回答
0
(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。
于 2012-12-04T19:47:58.227 回答
0
(Log n)^2 更好，因为如果您通过 exp m 对 n 进行变量更改，则 m^2 优于 exp m
于 2012-12-04T19:48:43.720 回答
-1
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)]
于 2012-12-04T19:47:30.640 回答