Big-O 和 Little-O 表示法之间的区别

f ∈ O(g) 说，本质上

对于常数 k > 0 的至少一个选择，您可以找到一个常数 a，使得不等式 0 <= f(x) <= kg(x) 对于所有 x > a 都成立。

请注意，O(g) 是该条件成立的所有函数的集合。

f ∈ o(g) 说，本质上

对于常数 k > 0 的每一个选择，您都可以找到一个常数 a，使得不等式 0 <= f(x) < kg(x) 对于所有 x > a 都成立。

再次注意，o(g) 是一个集合。

在 Big-O 中，您只需要找到一个特定的乘数 k，对于该乘数 k，不等式在某个最小值 x 之外仍然成立。

在 Little-o 中，必须存在一个最小值 x，在该最小值之后，无论您使 k 多么小，只要它不是负数或零，不等式都成立。

这些都描述了上限，虽然有点违反直觉，但 Little-o 是更强的陈述。如果 f ∈ o(g) 与 f ∈ O(g) 相比，f 和 g 的增长率之间的差距要大得多。

差异的一个例子是：f ∈ O(f) 为真，但 f ∈ o(f) 为假。因此，Big-O 可以理解为“f ∈ O(g) 意味着 f 的渐近增长不快于 g's”，而“f ∈ o(g) 意味着 f 的渐近增长严格慢于 g's”。这就像 <= 与 <。

更具体地说，如果 g(x) 的值是 f(x) 值的常数倍，则 f ∈ O(g) 为真。这就是为什么在使用 big-O 表示法时可以删除常量的原因。

但是，要使 f ∈ o(g) 为真，那么 g 必须在其公式中包含更高的 x 幂，因此 f(x) 和 g(x) 之间的相对分离实际上必须随着 x 变大而变大。

要使用纯数学示例（而不是指算法）：

以下对于 Big-O 是正确的，但如果您使用 little-o，则不正确：

x² ∈ O(x²)

x² ∈ O(x² + x)

x² ∈ O(200 * x²)

以下情况适用于 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 视为 <）

---

Big-O 对 little-o 就像 ≤ 对 <。 Big-O 是一个包容性的上界，而 little-o 是一个严格的上界。

例如，函数 f(n) = 3n 是：

在 O(n²)、o(n²) 和 O(n) 中

不在 O(lg n)、o(lg n) 或 o(n) 中

类似地，数字 1 是：

≤ 2、< 2 和 ≤ 1

不 ≤ 0、< 0 或 < 1

这是一张表格，显示了总体思路：

https://i.stack.imgur.com/SZ7jy.png

（注意：该表是一个很好的指南，但它的限制定义应该根据 superior limit 而不是正常限制。例如，3 + (n mod 2) 永远在 3 和 4 之间振荡。它在 O(1) 中，尽管没有正常限制，因为它仍然有 lim sup: 4。）

我建议记住 Big-O 表示法如何转换为渐近比较。比较更容易记住，但不太灵活，因为你不能说像 nO(1) = P 这样的东西。

---