0

我真的不知道如何用大 O 表示法表达。我已经看到几个消息来源在谈论这个，但这只会让我更加不确定。当我用 big-O 编写时，我应该忽略常量吗？

例子：

1. 0.02N³
2. 4N*log(2^N)
3. 24Nlog(N)
4. N²
5. N*sqrt(N)

这就是我所说的“忽略常量”：

1. O(N³)
2. O( N*log(2^N) )
3. O( Nlog(N) )
4. O( N² )
5. O( N*sqrt(N) )

与其他示例相比，增长速度O( N*log(2^N) )和增长速度如何？O( N*sqrt(N) )

我非常感谢您的帮助，因此在此先感谢

4

2 回答 2

4

大 O 表示法表征函数的渐近行为。数学f(x) = O(g(x))上当lim (x->inf) (f(x)/g(x)) = const

让我们弄清楚一点。有 5 种常用符号（Bachmann-Landau 符号）：

 ω (small omega)
 Ω (big omega)
 Θ (theta)
 Ο (big o)
 ο (small o)

它们像数学比较运算符一样工作：

 < (strictly less)
 <= (less or equals)
 = (equals)
 >= (greater or equals)
 > (strictly greater)

严格来说，大 o 只是一个上限，因此您不能仅根据大 o 符号来判断哪个函数增长得更快。

例如，快速排序的最坏情况复杂度 = O(n 2 )，但也可以说快速排序的最坏情况复杂度 = O(n 889 )。就像我们可以根据 x < 2 的知识说 x < 899。

由于限制行为，您可以忽略函数的常量和低阶加数（它们由最高阶加数“支配”）。例如，如果f(x) = 33*n³ + n² + n + 3544，那么说f(x) = O(n³) （此外，说f(x) = Θ(n³)哪个提供更多信息（Θ称为 a tight bound）是正确的

于 2013-01-12T16:20:51.907 回答
0

Yes, you ignore the constants. Also if you have a sum ex. 5n^2 + 2n you only take the biggest argument with highest exponent (also without the constant) -> here: O(n^2)
You did those examples good.

To compare the growing, I suggest you use wolframalpha or any tool drawing plots, and you will see how they change

于 2013-01-12T16:10:49.607 回答