渐近复杂度与主定理

复杂度是衡量算法的尺子。本章讲大 O、Ω、Θ 的定义，递归式的三种求解方法（代入法、递归树、主定理），常见复杂度类的直观规模，以及常数因子何时重要。

渐近记号

严格定义： $f(n) = O(g(n))$ 表示存在常数 $c, n_0$ ，使 $n > n_0$ 时 $f(n) \le c \cdot g(n)$ 。三个使用规范：

渐近记号隐藏常数与低阶项—— $3n^2 + 100n = O(n^2)$ 。这在算法比较时是特性（聚焦增长趋势），在工程判断时是陷阱（见下文"常数何时重要"）。
说 $O$ 时通常指最坏情况：快排最坏 $O(n^2)$ 、平均 $O(n \log n)$ ，两个数各有用处，混用会出错。
输入规模 $n$ 的定义要明确：对数算法说" $O(\log n)$ "时， $n$ 是数值还是位数差一个指数——判断素数的朴素算法是 $O(\sqrt{n})$ （按数值），按输入位数是 $O(2^{b/2})$ （指数）。密码学的"安全强度"永远按位数说（→ 公钥密码与密钥交换）。

分治算法（→ 分治）的代价写成递归式 $T(n) = aT(n/b) + f(n)$ 。三种解法：

猜出答案（如 $O(n \log n)$ ），用归纳法验证并确定常数。最可靠，但需要先猜对。

把递归展开成树：每层代价 $f$ 之和，深度 $\log_b n$ ，逐层求和取近似。最直观，是主定理的推导来源。

对 $T(n) = aT(n/b) + f(n)$ （ $a \ge 1, b > 1$ ），比较 $f(n)$ 与 $n^{\log_b a}$ ：

$f(n) = O(n^{\log_b a - \varepsilon})$ ： $T(n) = \Theta(n^{\log_b a})$ （叶子主导）；
$f(n) = \Theta(n^{\log_b a} \log^k n)$ ： $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$ （逐层均匀）；
$f(n) = \Omega(n^{\log_b a + \varepsilon})$ （正则条件）： $T(n) = \Theta(f(n))$ （根主导）。

例：归并排序 $T(n) = 2T(n/2) + \Theta(n)$ ， $n^{\log_2 2} = n$ ，第二类得 $\Theta(n \log n)$ 。

主定理只覆盖 $T(n) = aT(n/b) + f(n)$ 形式：子问题规模不均（如 $T(n) = T(n/3) + T(2n/3) + n$ ）或非常规（ $T(n) = \sqrt{n}\,T(\sqrt{n}) + n$ ）要回到递归树或代入法。

经验法则：每秒 $10^8$ 次基本操作。竞赛与工程估算都用这张表—— $O(n^2)$ 在 $n = 10^5$ 时已经不可行，必须找 $O(n \log n)$ 或 $O(n)$ 。

渐近分析忽略常数，但工程上常数真实存在：

小输入： $O(n \log n)$ 的归并排序在小数组上输给 $O(n^2)$ 的插入排序——低阶项与常数在 $n < 30$ 时主导。这就是内省排序与 TimSort 在小区间切换插入排序的原因（→ 排序与查找）。
缓存与向量化：理论更慢但缓存友好的算法（B+ 树 vs 红黑树）在实际中常胜（→ 二叉搜索树与平衡树）。
正确的用法：用渐近记号做"增长趋势"的判断，用基准测试做常数因子的判断——两者缺一不可（→ 性能工程与可观测性）。