问题描述
大O 标记 O(N)
和小-O 标记<之间$有什么区别C $ C> O(N)?
推荐答案
F∈O(G)说,基本上
f ∈ O(g) says, essentially
对于至少有一个选择恒定的 K 的> 0,你可以找到一个恒定的在的,这样的不平等F(X) &LT; ķG(x)的成立对于所有的x>一。
需要注意的是O(G)是一套此条件成立。
Note that O(g) is the set of all functions for which this condition holds.
F∈O(G)说,基本上
f ∈ o(g) says, essentially
对于每次选择恒定的 K 的> 0,你可以找到一个恒定的在的,这样的不平等F(X)&LT; ķG(x)的成立对于所有的x>一个。
再次,注意O(G)是一组。
Once again, note that o(g) is a set.
在大澳,重要的是你找到一个特定的乘数仅需要的 K 的用于该不等式成立超出某个最小的 X 的。
In Big-O, it is only necessary that you find a particular multiplier k for which the inequality holds beyond some minimum x.
在小-O,它必须有一个最低的 X 的在此之后,不等式成立,无论你多么小制作的 K 的,只要它不负或为零。
In Little-o, it must be that there is a minimum x after which the inequality holds no matter how small you make k, as long as it is not negative or zero.
这些都描述了上限,虽然有点与直觉相反,小-O是强硬的声明。还有就是f和g若f∈O(G)比若f∈O(G)的增长率之间存在多大差距较大。
These both describe upper bounds, although somewhat counter-intuitively, Little-o is the stronger statement. There is a much larger gap between the growth rates of f and g if f ∈ o(g) than if f ∈ O(g).
差距的一个例证是这样的:F∈O(F)是真实的,但˚F∈O(F)是假的。因此,大O可以被解读为F∈O(G)是指使得f的渐进增长不会高于G的,而F∈O(G)是指使得f的渐进增长严格小于G的要慢。这就像&LT; =
与&LT;
One illustration of the disparity is this: f ∈ O(f) is true, but f ∈ o(f) is false. Therefore, Big-O can be read as "f ∈ O(g) means that f's asymptotic growth is no faster than g's", whereas "f ∈ o(g) means that f's asymptotic growth is strictly slower than g's". It's like <=
versus <
.
更具体地,如果g(x)的值设为f(x)的值的常数倍,则f∈O(克)为真。这就是为什么你可以用大O表示法工作时掉落的常量。
More specifically, if the value of g(x) is a constant multiple of the value of f(x), then f ∈ O(g) is true. This is why you can drop constants when working with big-O notation.
不过,对于f∈O(G)是真实的,则g必须包括一个更高的动力的中X的配方,和f(x)和B(X之间,相对分离)必须真正得到较大的为x变大。
However, for f ∈ o(g) to be true, then g must include a higher power of x in its formula, and so the relative separation between f(x) and g(x) must actually get larger as x gets larger.
要使用纯数学的例子(而不是指算法):
To use purely math examples (rather than referring to algorithms):
以下是适用于大澳,但如果你使用的小邻不会是真实的:
The following are true for Big-O, but would not be true if you used little-o:
- X ^ 2∈O(X ^ 2)
- X ^ 2∈O(X ^ 2 + X)
- X ^ 2∈O(200 * X ^ 2)
以下是适用于小-O:
- X ^ 2∈O(X ^ 3)
- X ^ 2∈Ø(X!)
- LN(X)∈O(X)
请注意,若f∈O(G),这蕴涵f∈O(G)。例如X ^ 2∈O(X ^ 3),所以它也确实是x ^ 2∈O(X ^ 3),(同样,认为澳为&LT; =
与邻为&LT;
)
Note that if f ∈ o(g), this implies f ∈ O(g). e.g. x^2 ∈ o(x^3) so it is also true that x^2 ∈ O(x^3), (again, think of O as <=
and o as <
)
这篇关于大O和小O符号的区别的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!