渐进分析：大 O、Ω、Θ 与增长阶
一句话定义
渐进分析（Asymptotic Analysis）忽略常数因子与低阶项，用增长阶（如 O(n)、O(n log n)）刻画运行时间或空间随输入规模 n 增大的变化趋势；O 给上界，Ω 给下界，Θ 给紧确界。
为什么重要
机器型号、编译器、常数优化都会变，唯有「随规模增长的趋势」是算法自身的属性。没有渐进语言，你就只能说「我的机器上它快一点」；有了它，你能在写代码前就判断：10⁶ 规模下 O(n²) 的方案必死，O(n log n) 的方案安全。这也是面试与工程评审的通用语言——本库所有复杂度结论都用它表述。
前置知识
kp-001；对数与指数的基本运算（log₂n、2ⁿ 的量级感觉）。
核心概念
- 形式定义：f(n) = O(g(n)) 当且仅当存在常数 c > 0 与 n₀，使得对一切 n ≥ n₀ 有 f(n) ≤ c·g(n)。Ω 为下界（f ≥ c·g），Θ 同时满足两者（紧确）。
- 常见阶谱（由低到高）：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)。相邻两阶在 n=10⁶ 时可差数千至数十亿倍。
- 对数底数不重要：log₂n = (ln n)/(ln 2)，换底只差常数因子，故渐进记号中一律写 log n。
- 运算法则：顺序执行取加法（保留最高阶：O(n)+O(n²)=O(n²)）；嵌套执行取乘法；条件分支取最坏分支。
- 最好/最坏/平均：同一算法不同输入可对应不同函数，渐进记号只描述「给定输入类」的增长阶，口径必须在 kp-004 中进一步区分。
原理与机制
渐进分析的推理链有固定四步：①确定随输入变化的规模变量 n；②数出基本操作次数关于 n 的函数（顺序相加、嵌套相乘、递归交给 kp-003）；③取最高阶项并去掉系数——当 n 足够大时最高阶项支配总和，这正是「可以忽略低阶项与常数」的依据；④声明口径（最坏/均摊/期望）。忽略常数在「渐进」意义上是严格的数学结论，在逼近时限的工程场景里则需另行评估常数。
直观类比
比较两辆车不能只比 0–100 加速（常数项），要看高速巡航下的「速度—油耗曲线随载重如何恶化」：载重（n）翻倍时，A 车油耗翻倍 O(n)，B 车翻四倍 O(n²)——载重小的时候 B 甚至更省，载重一大必然被 A 反超。
公式或模型
- 加法/乘法法则：T₁(n)+T₂(n) = O(max(g₁(n), g₂(n)))；T₁(n)·T₂(n) = O(g₁(n)·g₂(n))。
- 常见来源模型：二分折半 ⇒ log n；外层 n 次 × 内层每次 O(1) ⇒ n；「n 层递归树、每层合并代价 n」⇒ n log n；两层独立枚举 ⇒ n²。
- 量级对照（约每次操作 1ns，一秒 = 10⁹ 次）：
| n | O(log n) | O(n) | O(n log n) | O(n²) |
|---|---|---|---|---|
| 10³ | 10 | 10³ | 10⁴ | 10⁶ |
| 10⁶ | 20 | 10⁶ | 2×10⁷ | 10¹²（约 17 分钟以上，实际更久） |
图示
增长速度（纵轴：操作数，示意）
n! ▲ ／
2^n | ／
n^2 | ／
n log n | ／
n | ／———————
log n | ／——
O(1) |——
└────────────────────────────────▶ n曲线在「某个 n 之后」永久分层，这正是 n₀ 存在的直观含义。
实例或案例
- 在无序数组找最大值：n−1 次比较，Θ(n)。
- 逐对比较所有元素找重复：双层循环，Θ(n²)。
- 先排序再线性扫一遍找重复：排序 O(n log n) + 扫描 O(n) = O(n log n)——同样的问题，换算法阶数从平方降到线性对数。
常见误区
- 把 O 当精确运行时间：O 只刻画增长趋势，忽略常数与低阶项；两个 O(n log n) 的排序实际速度可以差好几倍。
- 数循环层数定阶数：循环次数依赖数据的（如 while 循环每次 n/2）要按变量变化分析，不能机械数层。
- 低估常数工程意义：「O(2n)=O(n)」在渐进上对，但当你已逼近时限/时限时，常数就是生死线。
- 混用最坏与平均口径而不声明，导致比较失去意义。
自测题
- 证明 3n² + 100n + 500 = O(n²)，并给出一个可用的 c 与 n₀。
答案要点：取 c=4、n₀=500 时 3n²+100n+500 ≤ 4n² 成立（100n+500 ≤ n² 在 n≥500 时成立）。
- 为什么说 log n 来自「折半」？写出 n 折半到 1 所需次数的表达式。
答案要点：n/2^k = 1 ⇒ k = log₂n，每次折半一步，故折半过程为 O(log n)。
- n = 10⁶ 时，O(n²) 与 O(n log n) 的操作数差多少个数量级？
答案要点：10¹² 对约 2×10⁷，差约 4～5 个数量级，前者不可行、后者可行。
与其他知识点的关系
kp-003 把渐进分析扩展到递归式；kp-004 区分最坏/均摊/期望口径；kp-022 的二分与 kp-020 的排序下界都是本节模型的直接应用。
延伸阅读
《算法导论》第 3 章「函数的增长」；MIT 6.006 第 1–2 讲（渐进复杂度与文档距离示例）。