渐进符号与函数增长率：Big-O、Ω、Θ 与严格比较
插画：原神官方
如果一次运行需要 $5n^2+3n+10$ 次基本操作，怎样用一个简洁表达式描述它的增长？为什么O(n²)、O(n³)都可以作为上界，而Θ(n²)更准确地表达它的阶？
本文从不等式理解渐进符号，再用比值、同底指数和变量替换比较函数。需要了解代码计数，并能读懂幂、对数和基本不等式。
1. 从具体次数到增长阶
令 $T(n)=5n^2+3n+10$。当n≥1时，有：
$$ 5n^2\le T(n)\le5n^2+3n^2+10n^2=18n^2 $$T被二次函数的两个固定倍数夹住，所以是Θ(n²)。高次项决定这里的增长阶，固定倍数与低次项仍影响实际工作量。
下面用 $f(n)=5n^2+3n$ 继续说明三种界；它相当于把上例的固定初始化成本单独拿出来观察。
2. O、Ω、Θ：上界、下界与紧确界
下面讨论最终非负的函数；涉及比值时，还要求分母最终为正。“最终”表示从某个门槛开始，对后面所有整数 $n$ 都成立。
2.1 O：能否用常数倍从上面压住
$$ f\in O(g) \quad\Longleftrightarrow\quad \exists c>0,\ \exists n_0,\ \forall n\ge n_0:\quad 0\le f(n)\le c g(n) $$逐字翻译：能找到一个固定倍数 $c$ 和一个起点 $n_0$，使得后面的 $f(n)$ 始终不超过 $c g(n)$。
例如 $f(n)=5n^2+3n$。当 $n\ge1$ 时，$3n\le3n^2$，因此：
$$ 5n^2+3n\le8n^2 $$取 $c=8,n_0=1$，就证明了 $f\in O(n^2)$。常数不必选得最小，但不能随 $n$ 改变。
固定常数与起始门槛的量词次序，在第4节进一步展开。
2.2 Ω：能否用常数倍从下面托住
$$ f\in\Omega(g) \quad\Longleftrightarrow\quad \exists c>0,\ \exists n_0,\ \forall n\ge n_0:\quad 0\le c g(n)\le f(n) $$同一个例子里，$5n^2\le5n^2+3n$，所以取 $c=5,n_0=1$ 即可证明 $f\in\Omega(n^2)$。
2.3 Θ：上下同时夹住
$$ f\in\Theta(g) \quad\Longleftrightarrow\quad \exists c_1,c_2>0,\ \exists n_0,\ \forall n\ge n_0:\quad 0\le c_1g(n)\le f(n)\le c_2g(n) $$合并刚才两条不等式：
$$ 5n^2\le5n^2+3n\le8n^2\qquad(n\ge1) $$所以 $5n^2+3n\in\Theta(n^2)$。这就是“同阶”的严格含义。
3. 小o与小ω：严格增长比较
分母最终为正时，可以用比值记忆：
$$ f\in o(g)\iff\lim_{n\to\infty}\frac{f(n)}{g(n)}=0, \qquad f\in\omega(g)\iff\lim_{n\to\infty}\frac{f(n)}{g(n)}=+\infty $$例如 $n\in o(n^2)$，因为比值为 $1/n\to0$；但 $3n$ 不属于 $o(n)$，因为比值恒为3。
$O$ 给出增长上界，小 o 则把“严格增长得更慢”表达得更精确。它们也可以直接用量词定义。对最终非负的f、最终为正的g：
$$ f\in o(g)\iff \forall c>0,\ \exists n_0,\ \forall n\ge n_0:\ 0\le f(n)<c g(n) $$ $$ f\in\omega(g)\iff \forall c>0,\ \exists n_0,\ \forall n\ge n_0:\ 0\le c g(n)<f(n) $$O只需找到一个够大的上界倍数；小o要求任何固定正倍数最终都压得住f。Ω与小ω也有对应区别。
| 比值的极限 | 可推出的结论 |
|---|---|
| 0 | f∈o(g)，因而也属于O(g) |
| 有限正数 | f∈Θ(g) |
| 正无穷 | f∈ω(g)，因而也属于Ω(g) |
比值未收敛时，还可以直接使用不等式。例如 $f(n)=n(2+\sin n)$ 的比值在1与3之间波动，仍有 $n\le f(n)\le3n$，所以f属于Θ(n)。
4. 固定常数与量词次序
$O$ 的定义顺序是：先找到固定的 $c,n_0$，再保证所有 $n\ge n_0$ 都满足不等式。不能对每个 n 临时选一个 c，也不能只检查100、1000、10000这几个数。可以把定义想成一份承诺：“从这个门槛以后，同一把尺子始终适用。”
若两个条件分别从 $N_1$ 和 $N_2$ 开始成立，合并时取 $\max(N_1,N_2)$，就能保证两个条件同时可用。
证明 $n^2\in O(n)$ 时若令c=n，相当于每个输入都换一把尺子。固定c后，只要取 $n>c$，就有 $n^2>cn$，所以这样的固定上界不存在。
5. 函数成员与函数集合
$O(g)$ 是一组函数组成的集合。$f\in O(g)$ 表示 f 是其中一个成员；$O(f)=O(g)$ 表示两个函数集合完全相同。这和“3属于整数集合”与“两个集合相等”的区别一样。课件也提醒，常见写法 $f(n)=O(g(n))$ 中的等号是习惯记法，不是普通数值等式。
例如：
$$ n\in O(n^2),\qquad\text{但}\quad O(n)\ne O(n^2) $$因为二次函数属于右边的集合，却不属于左边的集合。
集合相等需要两个包含方向。可以先理解“常数倍夹住就有相同的上界函数集合”，再展开完整证明。
进阶阅读：具体多项式的双向包含证明
先用一个具体例子说明：
$$ O(5n^2+3n)=O(n^2) $$第一步，证明左边包含于右边。任取 $h\in O(5n^2+3n)$。按定义，存在固定常数 $a>0$ 和门槛 $N$，在 $n\ge N$ 时有 $0\le h(n)\le a(5n^2+3n)$。于是当 $n\ge\max(N,1)$：
$$ 0\le h(n)\le a(5n^2+3n)\le8a n^2 $$新常数取 $8a$，说明 $h\in O(n^2)$。
第二步，证明右边包含于左边。任取 $h\in O(n^2)$，存在 $b>0$ 和门槛 $M$，使得 $0\le h(n)\le bn^2$。当 $n\ge\max(M,1)$ 时：
$$ 0\le h(n)\le bn^2\le b(5n^2+3n) $$所以 $h\in O(5n^2+3n)$。两个方向都成立，集合才相等。
进阶阅读：O(f+g)=O(max{f,g})及非负性条件
把具体的多项式推广为最终非负的函数 f、g，令 $m(n)=\max\{f(n),g(n)\}$。对非负数，较大的一项不超过两项之和，而两项之和不超过较大项的两倍：
$$ m(n)\le f(n)+g(n)\le2m(n) $$任取 $h\in O(f+g)$。从某个门槛开始，有 $0\le h(n)\le c(f(n)+g(n))\le2c m(n)$，所以 $h\in O(m)$。
反过来，任取 $h\in O(m)$。从某个门槛开始，有 $0\le h(n)\le d m(n)\le d(f(n)+g(n))$，所以 $h\in O(f+g)$。两个方向使用的门槛均再与非负性成立的门槛取最大值，就得到：
$$ O(f+g)=O(\max\{f,g\}) $$这也解释了分析顺序执行代码时，为什么可以用增长较快的部分概括总工作量。
这里非负性不能省略。若随意允许一正一负，例如 $f(n)=n,g(n)=-n$，两者相加会抵消，上面的夹逼关系就不成立。
也不需要先猜 f 和 g 谁最终更大；它们可能交替更大。$\max$ 是对每一个 n 取较大值，不是提前固定选一个函数。
6. 函数增长率速查与比较
本文log统一为log₂，固定指数和底数在函数比较中保持不变。对数的换底公式给出 $\log_a n=(\log_b n)/(\log_b a)$（a、b均大于1），因此单独的log因子只差常数倍。若log出现在指数里，仍应代回整个函数比较。
| 函数类型 | 例子 | 典型算法联系 |
|---|---|---|
| 常数 | 1、20 | 固定数量索引 |
| 对数 | log n、(log n)² | 折半过程与其组合 |
| 固定次幂 | nᵃ，a>0固定 | 扫描、成对比较 |
| 线性对数 | n log n | 比较排序的典型时间 |
| 准多项式示例 | n^(log₂ n) | 指数本身不固定 |
| 固定底数指数 | cⁿ，c>1固定 | 固定分支数的穷举 |
| 阶乘 | n! | 排列搜索 |
| 更快的指数 | 2^(n²)、2^(2ⁿ) | 巨大候选状态空间 |
对固定a>0、c>1，有严格增长关系：
$$ 1\prec\log n\prec n^a\prec c^n\prec n!, \qquad f\prec g\ \text{表示}\ f\in o(g) $$6.1 根号、常数和多项式
先看一个训练用函数：
$$ \sqrt{5n}=\sqrt5\,n^{1/2}\in\Theta(n^{1/2}) $$根号里面的5变成了固定系数，不会把它变成一次函数。类似地，$n+30\in\Theta(n)$。比较固定次幂时，次数较小的一方增长得更慢：
$$ \frac{n^a}{n^b}=\frac1{n^{b-a}}\to0\qquad(a<b) $$6.2 对数的固定次幂，慢于任何固定正幂
一个常用结论是，对固定常数 $k>0,\varepsilon>0$：
$$ \frac{(\log n)^k}{n^\varepsilon}\to0 $$为什么？令 $t=\log_2 n$，则分子变成 $t^k$，分母变成 $2^{\varepsilon t}$。这就变成“固定次数的多项式慢于固定底数大于1的指数函数”。
进阶阅读：用二项式展开证明多项式慢于指数
对整数t，取固定整数 $q>k$。当t≥q时，二项式展开中 $(1+d)^t$ 至少包含 $\binom tq d^q$ 这一项，其中 $d=2^\varepsilon-1>0$。固定q时该项为Θ(t^q)，所以t^k除以指数函数趋于0；非整数t用相邻整数夹住即可。
例如，比较 $n(\log n)^2$ 与 $n^{3/2}$，先约去共同的 n，只需比较 $(\log n)^2$ 和 $n^{1/2}$。前者更慢。
比较时先约去共同因子，再使用上述增长关系，就能把混合表达式拆成简单的幂与对数。
6.3 多项式与固定底数的指数
对固定 $a>0,b>1$，有 $n^a\in o(b^n)$。这里强调“固定”：$n^{\log n}$ 的指数随 n 变化，不能直接当成某个固定次数的多项式。
比较两个指数，例如 $3^n$ 和 $7^n$，可看比值 $(3/7)^n\to0$。它们虽然都叫指数函数，增长率仍不同。
6.4 把比较规则串成一个完整例子
把下面六个函数按严格增长率排列，可得到：
$$ \sqrt{5n}\ \prec\ n+30\ \prec\ n(\log n)^2\ \prec\ n^{3/2}\ \prec\ 3^n\ \prec\ 7^n $$这里 $u\prec v$ 表示 $u\in o(v)$。逐对解释，而不是只写一条顺序：
- 第一对化简为半次幂与一次幂。
- 第二对约去 n 后，比较常数量级与趋于无穷的对数平方。
- 第三对用“对数固定次幂慢于固定正幂”。
- 第四对用“固定次数多项式慢于固定底数指数”。
- 第五对看底数比值的 n 次幂。
如果只要求按相邻的 $O$ 关系排序，则允许出现同阶函数；同阶函数之间可以互相构成上界。
6.5 为什么阶乘快于任意固定底数指数
n!的后半段至少有n/2个因子，每个不小于n/2。对n≥2：
$$ n!\ge(n/2)^{n/2}, \qquad \frac{c^n}{n!}\le\left(\frac{c}{\sqrt{n/2}}\right)^n\longrightarrow0 $$因此cⁿ∈o(n!)。这里c固定；把c也当成n的函数时，应重新比较。
排序、查找、子集枚举与排列的可运行计数，统一见复杂度篇的代码与对照表。比较增长阶有助于选择算法，同时还需要考虑可达到的输入规模和实现常数。
7. 复杂指数的比较
函数排序的困难往往来自括号读错，而不是比较方法不足。
7.1 同底指数，可以先比较指数
对最终为正的函数，若 $A(n)-B(n)\to-\infty$，那么：
$$ \frac{2^{A(n)}}{2^{B(n)}}=2^{A(n)-B(n)}\to0 $$因此比较很大的指数函数时，可以把问题转移到指数上。不要真的把天文数字算出来。
7.2 取对数是比较工具，不是替换 O 记号的规则
对正数，底数大于1的对数保持大小顺序，但不能随意声称“两个函数的对数同阶，所以原函数同阶”。
例如 $\log_2(2^n)=n$、$\log_2(4^n)=2n$，对数同阶；原函数的比值却是 $2^{-n}\to0$。取对数之后还应回到原比值，或比较指数差。
7.3 把复杂函数改写成统一的形式
以 $t=\log_2 n$ 为辅助变量，可以把几类常见表达式改写为更容易比较的形式：
| 表达式 | 正确读法或等价形式 | 接下来可以问自己 |
|---|---|---|
| $2^{\sqrt{\log_2 n}}$ | $2^{\sqrt t}$，不是 $2\sqrt{\log_2 n}$ | 与 $n^a=2^{at}$ 比，指数差如何变化？ |
| $n(\log n)^3$ | n 乘对数的三次幂 | 与另一个 n 的幂比较时，能否先约去 n？ |
| $n^{\log_2 n}$ | $(2^t)^t=2^{t^2}$ | 不同候选函数也写成同底指数后，比较哪两项？ |
| $2^{n^2}$ | 指数是 $n^2$ | 不要误读成 $(2^n)^2=2^{2n}$ |
| $2^{2^n}$ | 指数本身是 $2^n$ | 与上一行比较时，可否先比较两个指数？ |
图中 $n=3$ 的数值只用于区分表达式，不是渐进排序依据。
7.4 一份可重复使用的排序流程
- 写清对数底数与指数括号，先把根号变成分数幂。
- 去掉固定系数，找出明显的同阶项。
- 相邻两项能约去公共因子时，先约去。
- 指数复杂时，统一底数，或令 $t=\log_2 n$。
- 对最终顺序逐对给出比值、指数差或已证明的比较规则。
数值表和程序可以排查抄写错误，但有限范围内的大小关系不证明渐进关系；过大的指数还容易让浮点数溢出。
进阶阅读：把几类复杂指数排成严格增长链
令 $t=\log_2 n$，则
$2^{\sqrt{\log_2 n}}=2^{\sqrt t}$， $n^{4/3}=2^{4t/3}$， $n^{\log_2 n}=2^{t^2}$。逐对比较指数差，可得到：
$$ 2^{\sqrt{\log_2n}}\prec n(\log_2n)^3 \prec n^{4/3}\prec n^{\log_2n} \prec2^n\prec2^{n^2}\prec2^{2^n} $$第一对的指数差为 $\sqrt t-t-3\log_2t\to-\infty$。
第二对约去n，比较 $t^3/2^{t/3}\to0$。
中间两对用 $4t/3-t^2\to-\infty$ 与 $t^2-2^t\to-\infty$。
最后两对比较n−n²及n²−2ⁿ，均趋于负无穷。
8. 易错点
O不要求最紧，Ω也不表示“最好情况”；它们是函数关系。固定倍数不能随n变化；证明集合相等要有两个方向。取对数保持正数之间的大小顺序，但对数同阶不意味着原函数同阶。
有限数值表可以发现抄写错误，却只检查了有限多个输入；渐进结论要求越过某门槛以后所有输入都满足条件。复杂指数还可能超出浮点表示范围。
9. 练习
练习1：哪些界成立
令 $f(n)=5n^2+3n+10$。判断它是否属于O(n²)、O(n³)、Ω(n)、Θ(n²)、Θ(n³)。
练习2：选常数
证明 $7n+20\in O(n)$ 与Ω(n)，给出常数和门槛。
练习3：成员与相等
$n\in O(n^2)$ 是否推出O(n)=O(n²)？给出否定或证明。练习4：量词错误
“对每个n，取c=n，就得到n²≤cn，因此n²∈O(n)”错在哪里？
练习5：带对数的次幂
比较 $n(\log_2n)^4$ 与 $n^{6/5}$，再比较 $2^{3n}$ 与 $2^{n^2}$。
练习6：对数同阶
$\log_2(2^n)$ 和 $\log_2(4^n)$ 同阶，能否推出原函数同阶？练习7：复杂指数与阶乘
比较 $n^{\log_2n}$ 与2ⁿ；比较3ⁿ与n!。写出比较方法。
练习8：数值实验
一个程序在n≤1,000,000时始终得到f(n)<g(n)。还缺少什么，才能证明f∈O(g)？若比值没有极限，是否就不能属于Θ？
10. 参考答案
- 前四个成立，最后一个不成立。n≥1时 $5n^2\le f(n)\le18n^2$；又有n≤n²≤n³。f/n³趋于0，无法建立正的三次下界。
- n≥1时 $7n\le7n+20\le27n$，上下常数可取7和27，门槛1。
- 不能，n²属于O(n²)，却不属于O(n)，因此两个集合不同。
- c必须先固定，再对所有足够大的n有效。任何固定c都会在n>c时被n²超过。
- 比值分别为 $(\log_2n)^4/n^{1/5}\to0$ 和 $2^{3n-n^2}\to0$，两对均是前者严格慢于后者。
- 不能，原比值为 $2^{-n}\to0$；对数上的常数倍差异被指数放大。
- 令t=log₂n，第一对比值为 $2^{t^2-2^t}\to0$。第二对用n!后半段下界证明3ⁿ/n!趋于0。
- 还需给出固定c与门槛之后对所有n的界。比值不收敛也可用不等式夹逼，如n(2+sin n)∈Θ(n)。
11. 后续学习与参考资料
下一篇：贪心算法入门使用这些分析语言说明排序与扫描的成本，并进一步证明输出最优。
参考：《Design and Analysis of Algorithms》第二讲02Analysis第15至26页的渐进定义、函数集合与比较关系；《第一次作业》的函数比较与集合等式主题。本文保留原笔记的常数证明、双向包含、统一底数和指数图例。
