O（n ^ 2）vs O（n（logn）^ 2） [英] O(n^2) vs O (n(logn)^2)

问题描述

是时间复杂度 O（n ^ 2）或 O（n（logn）^ 2）

我知道当我们简化它时，它变成

I know that when we simplify it, it becomes

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

和 logn < n ，但是 logn ^ 2 ？

推荐答案

n 仅比（ log n） ² n 小于0.49 ...

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

所以一般（日志 n） ² 对于较大的 n 更好...

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

但是由于这些 / em>（某事） - 总是留下常数因素，在您的情况下，可能无法确定哪种算法更好...

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 的小值的差异不会太大，容易被不包括在Big-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 ，（ log n） ² 获胜双手：

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

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