为O（n ^ 2）对为O（n​​（LOGN）^ 2） [英] O(n^2) vs O (n(logn)^2)

问题描述

时的时间复杂度为O（n ^ 2）或 O（N（LOGN）^ 2）更好？

Is time complexity O(n^2) or O (n(logn)^2) better?

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

I know that when we simplify it, it becomes

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

和 LOGN ＆LT; N ，但对于 LOGN ^ 2 ？

and logn < n, but what about logn^2?

推荐答案

N 仅小于（登录的N） ² 作为值的 N 小于0.49 ...

n is only less than (log n)² for values of n less than 0.49...

所以一般来说（登录的N） ² 是大型的ñ更好

So in general (log n)² is better for large n...

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

But since these O(something)-notations always leave out constant factors, in your case it might not be possible to say for sure which algorithm is better...

下面是一个曲线图：

（蓝线是 N 和绿线是（登录的N） ² ）

(The blue line is n and the green line is (log n)²)

注意，如何对 N 小的值的差别并不大，而且可能很容易被不包括在大O符号，在常量因素相形见绌

Notice, how the difference for small values of n isn't so big and might easily be dwarfed by the constant factors not included in the Big-O notation.

但对于大型的 N （登录的N） ² 胜手了：

But for large n, (log n)² wins hands down:

这篇关于为O（n ^ 2）对为O（n​​（LOGN）^ 2）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！