1. 概述
本文将简要介绍 大 O 记号（Big-O notation）与小 o 记号（Little-o notation）之间的区别。
两者都是用于描述函数或算法运行时间的渐近上界（asymptotic upper bound）。
关键区别在于：
- 大 O 记号可能是一个渐近紧确的上界
- 小 o 记号则是一个非渐近紧确的上界
为了理解这个区别，我们需要先了解什么是“渐近紧确”。
2. 数学定义
大 O 和小 o 的定义非常相似，但它们在上界的严格程度上有差异。
2.1. 大 O 记号
对于给定函数 $ g(n) $，记号 $ O(g(n)) $ 定义为：
存在正常数 $ c $ 和 $ n_0 $，使得对于所有 $ n \geq n_0 $，都有 $ 0 \leq f(n) \leq c g(n) $。
换句话说，**$ O(g(n)) $ 是一组函数，这些函数在足够大的 $ n $ 时都不超过 $ g(n) $ 的某个常数倍**。
⚠️ 注意：大 O 记号不关心 $ n < n_0 $ 时的行为，因为它是用来分析函数在 $ n \to \infty $ 时的增长趋势。
如下图所示：
图中函数 $ f(n) $ 是 $ O(g(n)) $ 的一个例子。在 $ n_0 $ 之后，$ f(n) $ 没有超过 $ g(n) $。
“等于”关系在这里表示渐近紧确性，即当 $ n $ 很大时，$ f(n) $ 与 $ g(n) $ 增长速度一致。
✅ 示例：
- $ 3n^3 = O(n^3) $：渐近紧确
- $ 3n = O(n^3) $：不是渐近紧确
2.2. 小 o 记号
小 o 记号用于表示一个非渐近紧确的上界，其定义为：
对任意正常数 $ c $，存在正常数 $ n_0 $，使得对所有 $ n \geq n_0 $，都有 $ 0 \leq f(n) < c g(n) $。
换句话说，**小 o 记号要求函数 $ f(n) $ 在任何常数倍下都严格小于 $ g(n) $**。
数学上还可以用极限形式表示：
$$ \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0 $$
✅ 小 o 是比大 O 更强的上界条件：
- 大 O 只需要存在一个 $ c $ 成立
- 小 o 要求对任意 $ c $ 都成立
可以类比为：
- $ f(n) = O(g(n)) \approx a \leq b $
- $ f(n) = o(g(n)) \approx a < b $
3. 示例说明
我们来看几个具体的例子，帮助理解两者的区别。
3.1. 示例一
设 $ f(n) = 2n + 3 $
- ✅ $ f(n) = O(n) $，但 ❌ $ f(n) \ne o(n) $
- ✅ $ f(n) = O(n^2) $，✅ $ f(n) = o(n^2) $
- ✅ $ f(n) = O(n^3) $，✅ $ f(n) = o(n^3) $
3.2. 一般情况
设 $ f(n) = a_x n^x + a_{x-1} n^{x-1} + \dots + a_0 $
- ✅ $ f(n) = O(n^x) $，但 ❌ $ f(n) \ne o(n^x) $
- ✅ $ f(n) = O(n^{x+1}) $，✅ $ f(n) = o(n^{x+1}) $
- ✅ $ f(n) = O(n^{x+2}) $，✅ $ f(n) = o(n^{x+2}) $
✅ 小结：当 $ f(n) $ 的增长阶次小于 $ g(n) $ 时，它既是大 O 也是小 o；但当增长阶次相等时，它只能是大 O，不能是小 o。
4. 总结
- 大 O 记号用于描述函数的上界，可能渐近紧确
- 小 o 记号用于描述函数的非渐近紧确上界，更严格
- 小 o 是大 O 的真子集，即：小 o ⊂ O
⚠️ 踩坑提醒：在实际算法分析中，大 O 更常用，因为它更宽泛；而小 o 更适合用于强调函数增长远慢于另一个函数。
希望这篇文章能帮你理清这两个常见但容易混淆的渐近记号。