第02章 算法分析：大 O 记号与运行时间估算

这一篇在干嘛？

算法写出来能跑，不代表它”好”——数据量一大，$O(N^3)$ 的程序可能要跑两年半。本章建立一套数学语言（大 O 及其亲戚），让你在写代码之前就能算出程序在百万级数据上的表现。这是全书每一章都在用的分析工具。

2.1 四个记号：不只是大 O

用 $T(N)$ 表示”输入规模为 $N$ 时的运行时间”，四个定义层层递进：

大 O（渐进上界）：$T(N)=O(f(N))$，当且仅当存在常数 $c$ 和 $n_0$，使 $N\ge n_0$ 时 $T(N)\le c\cdot f(N)$。

白话：$f(N)$ 是增长率的”天花板”——数据够大之后，$T(N)$ 不会比 $cf(N)$ 涨得更快。日常口语里的”这个算法是 $O(N\log N)$ 的”指的就是上界。

大 Ω（渐进下界）：$T(N)=\Omega (g(N))$，当 $N\ge n_0$ 时 $T(N)\ge c\cdot g(N)$。大 Θ（渐进精确界）：同时满足 $O$ 和 $\Omega$，$T(N)=\Theta (h(N))$，不多不少正好这个增长率。小 o（非紧上界）：$T(N)=o(p(N))$ 表示 $T(N)<c\cdot p(N)$ 对任意常数 $c$ 都成立（比上界更”严”）。

一条速记：$T(N)=O(f(N))$ 相当于 $T(N)\le f(N)$，$\Omega$ 相当于 $\ge$，$\Theta$ 相当于 $=$，$o$ 相当于 $<$。

三条实用法则：

• 若 $T_1(N)=O(f(N))$ 且 $T_2(N)=O(g(N))$，则顺序执行两段代码合计 $O(f(N)+g(N))$（取更快的增长率，即 max）；嵌套执行合计 $O(f(N)\cdot g(N))$。
• 若 $T(N)$ 是 $k$ 次多项式，则 $T(N)=\Theta (N^k)$（低阶项在渐进意义下可忽略）。
• ${\log }^{k}N=O(N)$ 对任意常数 $k$ 成立——对数再乘几次方，也追不过线性。

常见坑

大 O 是上界不是”等于”。说”某算法最坏 $O(N^2)$、最好 $O(N)$“没问题，但把平均 $O(N\log N)$ 的快排说成”就是 $O(N^2)$“是把上界当成了增长率本身；反过来，能说 $\Theta$ 时别只给 $O$——信息量完全不同。

2.2 模型与分析什么

分析采用简化的计算模型：一行简单语句耗时一个时间单位、内存无限、没有”地址离得远就更慢”之类的存储层级效应。粗糙，但足够比较算法的量级。

要分析的量：

• 最坏情形 $T_{worst}(N)$：上界保证，最常分析——“承诺最惨也不会超过多少”。
• 平均情形 $T_{avg}(N)$：对输入分布取期望，往往和最坏差不多量级，但数学上更难。
• 最好的情形基本没意义（输入恰好特殊，不代表算法能力）。

2.3 经典案例：最大子序列和的四种解法

问题：给定整数 $A_1,\dots ,A_N$（可为负），求 ${\max }_{1\le i\le j\le N}{\sum }_{k=i}^j{A}_k$（子序列和全为负时答案为 0）。

算法 1：三重暴力 $O(N^3)$——枚举所有 $(i,j)$ 再逐个求和：

int maxSubSum1(const vector<int> &a) {
    int maxSum = 0;
    for (int i = 0; i < a.size(); ++i)          // 起点
        for (int j = i; j < a.size(); ++j) {    // 终点
            int thisSum = 0;
            for (int k = i; k <= j; ++k)        // 逐个加：重复劳动！
                thisSum += a[k];
            if (thisSum > maxSum)
                maxSum = thisSum;
        }
    return maxSum;
}

算法 2：去掉第三重循环 $O(N^2)$——发现 ${\sum }_{k=i}^j{A}_k={\sum }_{k=i}^{j-1}{A}_k+A_j$，内层求和可以顺水推舟，不必从头算。

算法 3：分治 $O(N\log N)$——把数组从中间劈成两半，最大子序列只有三种可能：全在左半、全在右半、跨越中线。前两种递归求解；第三种从中线向左、向右各扫一遍取最大延伸（两个 $O(N)$ 循环）。递推关系 $T(N)=2T(N/2)+O(N)$，由主定理解得 $O(N\log N)$。

算法 4：一次扫描（Kadane） $O(N)$——兼有最简形式与最高效率，也最不显然：

int maxSubSum4(const vector<int> &a) {
    int maxSum = 0, thisSum = 0;
    for (int j = 0; j < a.size(); ++j) {
        thisSum += a[j];               // 把当前元素并入"当前段"
        if (thisSum > maxSum)
            maxSum = thisSum;          // 记录历史最佳
        else if (thisSum < 0)
            thisSum = 0;               // 当前段已为负：立刻弃掉，从下一元素重新开段
    }
    return maxSum;
}

白话：一路累加，一旦”当前段的和”变成负数，它对后面任何延伸都是拖累——果断扔掉、重新开始。任意时刻只要扫过一遍，最优答案必然在某次”当前段”中出现过。

四种算法实测对比（原书 Figure 2.2，单位秒）：

输入规模	算法1 $O(N^3)$	算法2 $O(N^2)$	算法3 $O(N\log N)$	算法4 $O(N)$
N=100	0.000159	0.000006	0.000005	0.000002
N=1,000	0.095857	0.000371	0.000060	0.000022
N=10,000	86.67	0.033322	0.000619	0.000222
N=100,000	NA（约 9000s）	3.33	0.006700	0.002205
N=1,000,000	NA	NA（约 333s）	0.074870	0.022711

白话：N 扩大 10 倍，线性算法时间也只扩 10 倍；二次算法涨 100 倍；三次算法涨 1000 倍——从”眨眼完成”到”两小时起步”，差距全在增长率。另外注意：对线性算法，读入数据本身往往比求解还慢——好算法不该让计算成为瓶颈。

2.4 运行时间估算四法则

分析一段代码，按下面四条机械地算：

1. 简单语句（赋值、无输入输出的简单调用）：$O(1)$。for 循环头自身的比较和自增也并入循环体。
2. for 循环：循环体时间 × 迭代次数。一般 $n$ 次循环就是 $O(n)$。
3. 嵌套循环：由内向外逐层分析，总时间 = 各层迭代次数的乘积。双层 0..N 循环就是 $O(N^2)$。
4. 顺序语句 / if-else：取各分支中的最大值，不再相加。

一个会”骗人”的例子——计算 ${\sum }_{i=1}^N{i}^3$ 的程序：

sum = 0;
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= i; ++j)    // 注意内层上限是 i 不是 n！
        sum++;

内层迭代 $i$ 次、外层 $N$ 次，总量 ${\sum }_{i=1}^{N}i=N(N+1)/2$，所以是 $O(N^2)$ 而非 $O(N^3)$——嵌套循环要看清”内层跑多少圈”。

2.5 对数级复杂度的三种来源

判据：某算法是 $O(\log N)$，通常因为它每一步把问题规模砍掉一个常数比例（折半、砍 1/3……）。三种典型形态：

① 折半查找（binary search） $O(\log N)$：有序数组里找 x，与中点比较，每次排除一半。前提是数组已排序（排序本身要 $O(N\log N)$，所以输入静态且多次查询时才划算）。

② 欧几里得算法（gcd） $O(\log N)$：$\gcd (M,N)=\gcd (N,M\mathrm{mod}N)$，余数每两轮至少减半，故为对数级。这是”对数来源=余数递减”的变体：

long gcd(long m, long n) {
    while (n != 0) {
        long rem = m % n;   // 辗转相除
        m = n;
        n = rem;
    }
    return m;
}

③ 快速幂（exponentiation） $O(\log N)$：算 $X^N$，利用 $X^N=X^{N/2}\cdot X^{N/2}$（N 为偶数）或 $X\cdot X^{(N-1)/2}\cdot X^{(N-1)/2}$（N 为奇数），递归深度即 $\log N$。朴素的连乘 $X^{N-1}$ 次则是 $O(N)$—— RSA 加解密的效率差距就在这一个算法上。

白话：凡是”每次把规模折半/取余缩小”的算法，循环次数都约为 ${\log }_{2}N$——10 亿次数据也就约 30 步。这是分析树、堆、并查集（$O(\alpha (N))$ 更快）等章节的直觉基础。

最坏情形分析的局限：有时最坏情形过度悲观（如快排平均 $O(N\log N)$ 但最坏 $O(N^2)$，实践中仍是最快的通用排序之一），也可能遇到病态输入（如对已排序输入做快速幂之类依实现而异的退化）。选取何种度量要结合场景，不能只背数字。

常见坑

把大 O 当”平均”用：$O$ 只是上界，快排最坏 $O(N^2)$、平均 $O(N\log N)$，描述时别混。另一个坑：嵌套循环默认 $O(N^2)$，但内层若是”折半”或”从 i 开始”，实际是 $O(N\log N)$ 或 $O(N^2)$ 的一半——常数减半不改变量级，但循环结构变了量级就变。

通关标准

学完本篇你应该能做到：① 说清 O/Ω/Θ/o 的区别并互相换算；② 对任意循环嵌套代码机械地算出大 O（含内层上限依赖外层变量的情形）；③ 讲出最大子序列和四种算法的思路与量级，并手写 Kadane 算法；④ 一眼识别对数级算法的三种来源模式。

为什么大 O 记号可以丢掉常数和低阶项？这样会不会掩盖真实性能差异？

大 O 只关心 N 足够大时的增长率。低阶项和常数在 N→∞ 时被主项吞没，不影响”谁的上限更高”的结论。但它确实掩盖常数差异：同为 O(N log N) 的两个算法实测可以差 3 倍——所以渐进分析用于选型级决策，常数优化靠实测。

算法 3（分治）的递推式 T(N)=2T(N/2)+O(N) 为什么解出来是 O(N log N)？

展开共 log N 层，每层所有子问题的”合并+扫描”工作量之和是 O(N)，故总时间 O(N·log N)。这就是主定理（master theorem）$T(N)=aT(N/b)+O(N^k)$ 在 a=2、b=2、k=1 时的情形。

Kadane 算法为什么敢把负的 thisSum 直接清零？

若当前段和为负，把它接到后面任何元素上都会让新段的和比”不接”更小，即它不可能出现在最优解中。清零等价于”最优段从此处重新开始”，不会漏解。

gcd 算法为什么是对数级的？

相邻两轮迭代后余数至少变为原来的一半（可由 $M\mathrm{mod}N<M-N$ 推出），所以迭代次数 $O(\log \min (M,N))$。

$2^{100}\mathrm{mod}5$ 怎么快速计算？

用快速幂在模运算下逐半平方：$2^{100}=(2^{50}{)}^2=((2^{25}{)}^2{)}^2=\dots$，每步取模防止数字爆炸，约 ${\log }_{2}100\approx 7$ 次乘法即可，而非 99 次连乘。