Asymptotic Notation Tips

核心结论

重要

渐进记号写在右边，通常表示“某个具体函数属于这个渐进函数集合”；写在左边，通常表示“对这个集合中的任意函数，右边结论都成立”。

渐进记号中的等号不是普通等号，而是一种单向记号滥用。

严格理解时，应把：

$$f(n)=O(g(n))$$

看作：

$$f(n) \in O(g(n))$$

---

1. 渐进记号写在右边

形式

$$f(n)=O(g(n))$$

含义

$$f(n) \in O(g(n))$$

即存在常数 $c>0,n_0>0$，使得当 $n\ge n_0$ 时：

$$0\le f(n)\le c g(n)$$

例子

$$2n^2=O(n^3)$$

严格含义是：

$$2n^2\in O(n^3)$$

表示 $2n^2$ 的增长速度不超过某个常数倍的 $n^3$。

---

2. 渐进记号写在表达式中

形式

$$f(n)=n^3+O(n^2)$$

含义

存在某个函数 $h(n)\in O(n^2)$，使得：

$$f(n)=n^3+h(n)$$

这里的 $O(n^2)$ 不是一个具体函数，而是一个未知但受 $n^2$ 控制的误差项。

例子

若：

$$f(n)=n^3+7n^2-3n+10$$

则：

$$f(n)=n^3+O(n^2)$$

因为：

$$7n^2-3n+10=O(n^2)$$

---

3. 渐进记号写在左边

形式

$$n^2+O(n)=O(n^2)$$

含义

对任意 $h(n)\in O(n)$，都有：

$$n^2+h(n)\in O(n^2)$$

即：

$$\forall h(n)\in O(n),\quad n^2+h(n)=O(n^2)$$

例子

以下都满足：

$$n^2+3n=O(n^2)$$ $$n^2+\log n=O(n^2)$$ $$n^2+100n=O(n^2)$$

所以 $n^2+O(n)=O(n^2)$ 表示：无论 $O(n)$ 代表哪一个线性级别的低阶项，整个表达式仍然是 $O(n^2)$。

---

4. 为什么不能左右交换

正确写法

$$2n^2=O(n^3)$$

因为：

$$2n^2\in O(n^3)$$

错误写法

$$O(n^3)=2n^2$$

原因：$O(n^3)$ 是一个函数集合，其中包含很多函数，例如：

$$n,\quad n^2,\quad n^3,\quad 100n^3$$

这些函数不可能都等于 $2n^2$。

---

5. 集合包含关系

有时会看到：

$$O(n)=O(n^2)$$

更严谨地说，它表示：

$$O(n)\subseteq O(n^2)$$

这是正确的，因为任何线性增长的函数也一定是二次增长的上界函数集合中的元素。

但反过来不成立：

$$O(n^2)\nsubseteq O(n)$$

因为：

$$n^2\in O(n^2),\quad n^2\notin O(n)$$

---

6. 常见写法对照

---

7. 写作建议

提示

在作业、考试和论文式表达中，优先使用更严谨的集合写法。

推荐：

$$f(n)\in O(g(n))$$

或常规写法：

$$f(n)=O(g(n))$$

避免：

$$O(g(n))=f(n)$$

对于集合关系，推荐写：

$$O(n)\subseteq O(n^2)$$

而不是：

$$O(n)=O(n^2)$$

---

一句话记忆

总结

渐进记号在右边，是给具体函数分类；渐进记号在左边，是对一类函数整体作断言。

相关笔记

• Asymptotic Notation & Analysis
• Introduction to Algorithms 算法导论
• Recurrences