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

Question

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

我知道,当我们简化它时,它就变成了

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

和logn< n,但是怎么样logn^2？

Answer 1

Ñ仅小于(登录 n)的²对的值Ñ小于0.49 ...

所以一般来说(log n)²对于大n来说更好...

但由于这些O(某些)注释总是会遗漏不变因素,在您的情况下,可能无法确定哪种算法更好......

这是一张图:

(蓝线为n,绿线为(log n)²)

注意,n的小值的差异不是那么大,并且可能很容易被Big-O表示法中未包含的常数因子相形见绌.

但对于大n,(log n)²获胜:

Answer 2

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

证明很简单,请记录等式的两边,然后得到:

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

很容易看出渐近地,这是正确的.

语义注释:假设在这里log(n)^k == log(n) * log(n) * ... * log(n) (k times)而不是log(log(log(...log(n)))..) (k times)因为它有时也被使用.