大O和小O符号的区别 [英] Difference between Big-O and Little-O Notation

问题描述

大O 标记 O（N）和小-O 标记<之间$有什么区别C $ C> O（N）？

推荐答案

F∈O（G）说，基本上

f ∈ O(g) says, essentially

对于至少有一个选择恒定的 K 的> 0，你可以找到一个恒定的在的，这样的不平等F（X） ＆LT; ķG（x）的成立对于所有的x>一。

For at least one choice of a constant k > 0, you can find a constant a such that the inequality f(x) < k g(x) holds for all x > 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，你可以找到一个恒定的在的，这样的不平等F（X）＆LT; ķG（x）的成立对于所有的x>一个。

For every choice of a constant k > 0, you can find a constant a such that the inequality f(x) < k g(x) holds for all x > a.

再次，注意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符号的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！