函数的增长：把“跑得快”变成可以证明的判断

一个配送系统每天要处理订单。方案 A 的操作数大约是 $40n\lg n$，方案 B 大约是 $n^2$。当 $n=100$ 时，两者都能很快结束；当 $n=1{,}000{,}000$ 时，前者约做 $7.97\times10^8$ 次操作，后者却要做 $10^{12}$ 次。此时，换一台快两倍的机器只能救下常数倍时间，换一个增长更慢的算法才会改变局面。

本章建立一套回答这类问题的语言：怎样忽略不影响长期趋势的细节，怎样区分上界、下界和紧确界，怎样用常数给出证明，以及怎样把代码的循环次数归到常见增长族中。

输入扩大后，增长阶决定算法能否继续扩展：$n\lg n$ 的任务量增长温和，$n^2$ 则会迅速形成数量级拥堵。

从精确秒数转向增长趋势

设输入规模为 $n$，算法在规模 $n$ 上的基本操作次数为 $T(n)$。精确的运行时间还受处理器、编译器、缓存、语言实现和输入分布影响。渐近分析先把这些因素放到一边，观察 $n$ 不断增大时，$T(n)$ 由哪一部分主导。

看一组真实计算结果：

Node.js v25.2.1
n | lg n | n lg n | n^2
10 | 3.322 | 33 | 100
100 | 6.644 | 664 | 10,000
1000 | 9.966 | 9,966 | 1,000,000
1000000 | 19.932 | 19,931,569 | 1,000,000,000,000

当规模从 $10^3$ 增至 $10^6$，$n\lg n$ 增到约两千万，而 $n^2$ 达到一万亿。常数因子在小规模上可能主导实际速度，规模继续增大后，增长阶通常会决定哪个方案更可扩展。

这不表示渐近分析能代替基准测试。它回答“规模扩大后会怎样”，基准测试回答“这台机器上的这份实现现在多快”。工程判断通常需要两者。

算法 A 做 $1000n$ 次操作，算法 B 做 $n^2$ 次操作。能否只根据渐近阶断言 A 对每个正整数 $n$ 都更快？

五种渐近记号各自说什么

以下定义都假设相关函数在足够大的 $n$ 上非负。这个条件适合操作次数、运行时间和空间占用，也使常数倍上下界有清楚的方向。

这五幅图使用同一观察方式：先越过阈值 $n_0$，再判断函数是否被常数倍夹住、只受单侧约束，或与参照函数持续拉开差距。

紧确界：$\Theta$

若存在正常数 $c_1,c_2,n_0$，使得每个 $n\ge n_0$ 都满足

则写作 $f(n)=\Theta(g(n))$。从 $n_0$ 开始，$f$ 被 $g$ 的两个固定常数倍夹住；两者在渐近意义下同阶。

上界：$O$

若存在正常数 $c,n_0$，使得每个 $n\ge n_0$ 都满足

则写作 $f(n)=O(g(n))$。它只承诺“最终不会高过某个常数倍”，不承诺这个界足够紧。例如 $n=O(n^2)$ 完全正确，但 $\Theta(n)$ 更准确地描述了 自身的增长。

下界：$\Omega$

若存在正常数 $c,n_0$，使得每个 $n\ge n_0$ 都满足

则写作 $f(n)=\Omega(g(n))$。它保证 $f$ 最终至少达到 $g$ 的某个固定常数倍。

上下界合在一起得到紧确界：

非紧上界与非紧下界：$o$ 和 $\omega$

$f(n)=o(g(n))$ 比 $f(n)=O(g(n))$ 更强：对任意给定的正常数 $c$，总能找到一个阈值，使之后都有 $f($。当比值极限存在时，可用

识别它。例如 $n=o(n^2)$。

$f(n)=\omega(g(n))$ 表示 $f$ 最终会超过 $g$ 的任意固定常数倍。当比值极限存在时，

例如 $n^2=\omega(n)$。

用常数见证一个渐近结论

渐近证明不是“删掉低阶项”这句话本身，而是找出能让定义成立的常数。以

为例，我们要证明 $f(n)=\Theta(n^2)$。

这组常数不需要最优：$n_0=1,c_1=3,c_2=6$ 已经足以让双边不等式对阈值后的全部输入成立。

程序逐点检查得到：

Node.js v25.2.1
n=1: 3 <= 6 <= 6: true
n=2: 12 <= 17 <= 24: true
n=5: 75 <= 86 <= 150: true
n=10: 300 <= 321 <= 600: true
n=100: 30000 <= 30201 <= 60000: true

有限个样本不能代替证明；这里的检查只用于发现算术错误。证明真正依赖的是“对所有 $n\ge1$”都成立的不等式。

一般地，若

且 $a_d>0$，那么 $p(n)=\Theta(n^d)$。原因是每个低阶幂 $n^i$ 在 时都不超过 ；选一个足够大的上界常数即可吸收所有系数。下界则可在阈值足够大后，让正的最高次项压过可能为负的低阶项。

证明 $5n^3+4n^2+7=\Theta(n^3)$。请给出一组可用的 $c_1,c_2,n_0$。

比较关系、转置与不可比较

把渐近记号当成增长关系，可以得到一组实用规则。假设函数最终为正：

• 传递性：若 $f=O(g)$ 且 $g=O(h)$，则 $f=O(h)$；$\mathrm{\Omega },\mathrm{\Theta },o,$ 也分别具有传递性。

这些关系很像实数的 $\le,\ge,=,<,>$，但有一个重要例外：函数不一定总能比较。

例如 $f(n)=n$，$g(n)=n^{1+\sin n}$。随着 $n$ 改变，指数在 $0$ 与 之间振荡， 会反复落到远低于 和远高于 的位置。因此不能用一个最终有效的常数倍关系断言 或 。

渐近等式也要谨慎阅读。$f(n)=O(g(n))$ 严格地说是在表达集合归属，而非两个函数数值相等。在更长的式子中，$O(g(n))$ 可以理解为“某个具体但无需命名、且属于这个集合的函数”。这种简写有助于隐藏不影响主线的低阶细节。

常见增长族与最终胜负

常见函数大致可按以下顺序从慢到快排列：

其中 $a,k>0$，$c>1$ 都是固定常数，$\prec$ 表示左边是右边的 $o$。

图中的早期交叉并不影响渐近排序；比较增长率时，观察的是规模足够大之后能否保持稳定的相对关系。

为什么对数底数常被省略

对任意固定底数 $a,b>1$，换底公式给出

$1/\log_b a$ 是常数，所以不同固定底数的对数属于同一个 $\Theta$ 类。二分算法常写 $\lg n$，只讨论增长阶时也常简写为 $\log n$。

多项式、指数和阶乘

任意固定次数多项式最终都会超过任意固定次数的多对数：

任意底数大于 $1$ 的指数函数又会最终超过任意固定次数多项式：

阶乘满足 $n!\le n^n$，并且它最终超过任意固定底数的指数函数。Stirling 近似还能给出

由此可见

极慢增长与递推数列

$\lg^*n$ 表示把 $\lg$ 反复作用到结果不大于 $1$ 所需的次数。它增长得极慢：$\lg^*2=1$、$$、、。

Fibonacci 数列虽然由加法递推，数值却呈指数增长。若 $\varphi=(1+\sqrt5)/2$，则

这提醒我们：判断增长阶要分析递推产生的总效果，不能只看单步用了加法还是乘法。

从代码数出增长阶

最稳妥的方法是先数关键操作次数，再化简。考虑：

def count_triples(n):
    count = 0
    for i in range(n):
        for j in range(i, n):
            for k in range(j, n):
                count += 1
    return count

关键操作与满足

的三元组一一对应，数量为可重复组合数：

展开后最高次项是 $n^3/6$，所以 $T(n)=\Theta(n^3)$。真实运行与公式一致：

Node.js v25.2.1
n=1: actual=1, formula=1, ok=true
n=2: actual=4, formula=4, ok=true
n=3: actual=10, formula=10, ok=true
n=5: actual=35, formula=35, ok=true
n=10: actual=220, formula=220, ok=true

不要只凭“有三层循环”立刻写 $\Theta(n^3)$。如果每层边界依赖前一层，或每次把索引乘二，次数可能不同。例如：

i = 1
while i < n:
    i *= 2

执行次数是满足 $2^t\ge n$ 的最小整数 $t$，因此为 $\lceil\lg n\rceil=\Theta(\lg n)$。

下面代码的增长阶是什么？

for i in range(n):
    j = 1
    while j < n:
        j *= 2

把最坏、最好与任意输入说清楚

同一个算法在同一规模的不同输入上可能运行不同时间。以插入式排序为例，已经有序的输入只需线性级检查，逆序输入会触发平方级移动。

• “最坏情况是 $\Theta(n^2)$”只描述每个规模中最慢的输入。
• “最好情况是 $\Theta(n)$”只描述每个规模中最快的输入。
• “运行时间是 $O(n^2)$”可以作为覆盖全部输入的上界，因为任何输入都不会比最坏情况更慢。
• 仅从“最坏情况是 $\Theta(n^2)$”不能推出“每个输入都是 ”。

综合练习

练习一：界是否紧

判断下列命题，并说明理由。

1. $4n+9=O(n^2)$。
2. $4n+9=\Theta(n^2)$。

练习二：构造证明

用定义证明 $2n^2-5n+8=\Theta(n^2)$。

练习三：代码计数

count = 0
for i in range(n):
    for j in range(i):
        count += 1

写出 count += 1 的精确执行次数和渐近阶。

练习四：增长率分组

把下列函数按 $\Theta$ 等价类从慢到快排列：

练习五：找出语言错误

有人说：“这个算法至少需要 $O(n^3)$ 时间，所以它一定很慢。”这句话有什么问题？

完成这些练习后，应能把一句含糊的“这个算法更快”拆成三个可检查的问题：比较的是哪种输入情形、使用的是上界还是紧确界、常数见证或计数式能否让结论真正成立。

又有 $4n^2\le4n^3$ 且 $7\le7n^3$，所以

因此可取 $c_1=5,c_2=16,n_0=1$。

同时 $-5n\le0$ 且 $8\le8n^2$，因此

可取 $c_1=1,c_2=10,n_0=5$。常数并非唯一。

所以顺序为