问题描述
Big-O 表示法 O(n) 和 Little-O 表示法 o(n)?
What is the difference between Big-O notation O(n) and Little-O notation o(n)?
推荐答案
f ∈ O(g) 说，本质上
f ∈ O(g) says, essentially
对于至少一个常量k > 0的选择，你可以找到一个常量a使得不等式0 a 成立.
请注意，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的选择，你可以找到一个常数a使得不等式0 a 成立.
再次注意 o(g) 是一个集合.
Once again, note that o(g) is a set.
在 Big-O 中，您只需要找到一个特定的乘数 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.
在 Little-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.
这些都描述了上限，尽管有点违反直觉，但 Little-o 是更强的陈述.如果 f ∈ o(g)，则 f 和 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) 为假.因此，Big-O 可以理解为f ∈ O(g) 意味着 f 的渐近增长不比 g 快"，而f ∈ o(g) 意味着 f 的渐近增长严格慢于 g".这就像 <= 与 <.
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(g) 为真.这就是为什么在使用大 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) 和 g(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):
以下适用于 Big-O，但如果您使用 little-o，则不适用:
The following are true for Big-O, but would not be true if you used little-o:
- x² ∈ O(x²)
- x² ∈ O(x² + x)
- x²∈O(200 * x²)
以下适用于 little-o:
The following are true for little-o:
- x²∈o(x³)
- x²∈o(x!)
- ln(x) ∈ o(x)
注意，如果 f ∈ o(g)，这意味着 f ∈ O(g).例如x² ∈ o(x³) 所以 x² ∈ O(x³) 也成立，(同样，把 O 看作 <= ，把 o 看作 <)
Note that if f ∈ o(g), this implies f ∈ O(g). e.g. x² ∈ o(x³) so it is also true that x² ∈ O(x³), (again, think of O as <= and o as <)
这篇关于Big-O 和 Little-O 表示法之间的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！