我如何写大O标记 [英] How do I write Big O-notations

问题描述

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

I don´t really know how to express in big O-notation. I´ve seen several sources talking about this but it only made me more uncertain. When I write in big-O should I just ignore the constants?

示例:

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

这就是我忽略常量"的意思:

this is what I mean with "ignore the constants":

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) )的增长速度有多快?

and how fast are O( N*log(2^N) ) and O( N*sqrt(N) ) growing compared to the other examples?

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

I really appreciate the help so thanks in advance

推荐答案

Big O符号表示函数的渐近行为.数学上f(x) = O(g(x))时lim (x->inf) (f(x)/g(x)) = const

Big O notation is characterizes asymptotic behavior of function. Mathematically f(x) = O(g(x)) when lim (x->inf) (f(x)/g(x)) = const

让我们弄清楚一些.共有5种常用符号(巴赫曼–朗道符号):

Let's get some clarity. There are 5 common notations (Bachmann–Landau notations):

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

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

They works like mathematical comparison operators:

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

严格地说，大o只是一个上限，因此您不能仅根据big-o表示法就说哪个函数增长更快.

Strictly saying, big o is just an upper bound so you can't say which function grows faster based just on big-o notation.

例如，快速排序的最坏情况复杂度= O(n ² )，但也可以说快速排序的最坏情况复杂度= O(n ⁸⁸⁹ ). 就像我们可以说x<基于x ＜899的知识. 2.

For example, quick sort has worst case complexity = O(n²) but it's also right to say that quick sort has worst case complexity = O(n⁸⁸⁹). It's just like we can say x < 899 based on knowledge that x < 2.

由于存在限制行为，因此可以忽略函数的常量和较少顺序的加数(它们由最高顺序的加数控制"). 例如，如果f(x) = 33*n³ + n² + n + 3544，则正确地说f(x) = O(n³) (此外，正确地说f(x) = Θ(n³)信息更正确(Θ被称为tight bound)

Because of the limiting behavior you can ignore constants and less-ordered summands (they are "dominated" by the highest order summand) of your functions. For example, if f(x) = 33*n³ + n² + n + 3544, it's right to say that f(x) = O(n³) (Moreover, it's right to say f(x) = Θ(n³) which is much more informative (Θ is called a tight bound)

这篇关于我如何写大O标记的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！