我如何写大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 2 ),但也可以说快速排序的最坏情况复杂度= O(n 889 ). 就像我们可以说x<基于x <899的知识. 2.
For example, quick sort has worst case complexity = O(n2) but it's also right to say that quick sort has worst case complexity = O(n889). 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屋!