1.2　大 O 记法：描述增长，而不是秒数

学习目标：学完本节，你能

对一段代码写出它的大 O 表达式；
熟练使用「去系数、留最高阶」两条化简规则；
说出常见量级在 $n$ 翻倍时各会涨几倍。

先修：1.1（输入规模、基本操作）。 固定术语：大 O 记法、渐进分析。 环境与版本：.NET 8 / C# 12。 预计阅读：25 分钟（含动手运行代码）。

一、直觉：为什么可以扔掉系数

上一节算出两种做法的代价分别是 $\frac{n^2}{2}$ 和 $n$。当时留了个问题：$\frac{n^2}{2}$ 里的 $\frac{1}{2}$ 重要吗？

把 $\frac{n^2}{2}$ 和 $n^2$ 放到不同的 $n$ 上比一比：

$n$	$\frac{n^2}{2}$	$n^2$	比值
1,000	500,000	1,000,000	2
10,000	50,000,000	100,000,000	2
100,000	5,000,000,000	10,000,000,000	2

比值恒为 2，永远不变。系数只决定"整体慢几倍"，不决定"增长方式"。

而我们真正该怕的是增长方式：数据涨 10 倍时，耗时是涨 10 倍还是 100 倍？至于它同时还"慢 2 倍"，那是次要问题 —— 优化系数只能救你一次，改变增长方式才能救你一辈子。

大 O 记法就是「只保留增长方式」的写法：$\frac{n^2}{2}$ 写成 $O(n^2)$。

这种忽略常数与低阶项、只看增长趋势的分析方法，叫作渐进分析（Asymptotic Analysis）。它是本书使用频率最高的工具 —— 后面每一节都会用到它。

二、形式化：定义与化简规则

定义（白话版）：如果存在一个正常数 $c$，使得当 $n$ 足够大以后总有

$$f(n) \le c \cdot g(n)$$

就记作 $f(n) = O(g(n))$，读作"$f(n)$ 是 $O(g(n))$ 的"，含义是：$f$ 的增长不会超过 $g$ 的某个固定倍数。

不用记符号细节，记住这一句就够：大 O 描述的是增长趋势的上界，不是精确值。

化简三规则：

规则	例子
① 去掉常数系数	$O(3n) = O(n)$；$O!\left(\frac{n^2}{2}\right) = O(n^2)$；$O(100) = O(1)$
② 只保留最高阶	$O(n^2 + n + 5) = O(n^2)$；$O(n^3 + 100n^2) = O(n^3)$
③ 加法取大，乘法相乘	$O(n) + O(n^2) = O(n^2)$；$O(n) \times O(n) = O(n^2)$

规则 ② 的道理：$n$ 很大时，$n^2$ 会远远盖过 $n$。$n = 10{,}000$ 时 $n^2 = 10^8$，而 $n$ 只有 $10^4$ —— 差了一万倍，$n$ 那一项有没有都无所谓了。

常见量级表（这张表值得记住）：

量级	名称	$n$ 翻倍时	典型场景
$O(1)$	常数	不变	数组按下标访问、哈希表查找
$O(\log n)$	对数	只多 1 次操作	二分查找
$O(n)$	线性	$\times 2$	一次遍历
$O(n \log n)$	线性对数	约 $\times 2.2$	好的排序算法
$O(n^2)$	平方	$\times 4$	两层嵌套
$O(2^n)$	指数	变成平方	枚举所有子集

$O(\log n)$ 那一行最值得琢磨：$n$ 翻倍只多一次操作。这就是为什么二分查找在上亿条数据里也只需要约 30 次比较。

符号约定：本书中 $\log n$ 一律指以 2 为底的对数。$n = 1000$ 时 $\log_2 1000 \approx 9.97$，循环实际执行 10 次。

三、例题：四段代码

例题 1：标准双层循环

for (int i = 0; i < n; i++)        // 执行 n 次
    for (int j = 0; j < n; j++)    // 每次又执行 n 次
        sum++;

$n \times n = n^2$，所以是 $O(n^2)$。

例题 2：内层次数依赖外层

for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
        sum++;

内层执行 $(n - i)$ 次，总计

$$n + (n-1) + \cdots + 1 = \frac{n(n+1)}{2} = \frac{n^2}{2} + \frac{n}{2}$$

去系数、去低阶，仍然是 $O(n^2)$。

注意：形如"内层依赖外层"的循环必须老老实实求和，不能想当然。如果内层条件换成 j < i * i，结论会完全不同。

例题 3：两个规模独立的输入

// a 有 m 个元素，b 有 n 个元素
foreach (var x in a)          // 执行 m 次
    foreach (var y in b)      // 每次执行 n 次
        Compare(x, y);

答案是 $O(m \times n)$ —— 不能写成 $O(n^2)$，因为 $m$ 和 $n$ 是两个互相独立的规模。这是初学者最常犯的错误之一。

例题 4：成倍增长

for (int i = 1; i < n; i *= 2)
    Console.WriteLine(i);

$i$ 依次取 1, 2, 4, 8, 16, …… 一共执行 $\log_2 n$ 次，所以是 $O(\log n)$。

识别信号：循环变量成倍变化（i *= 2、i /= 2、left = mid）就是 $O(\log n)$；逐步加减变化（i++、i += 3）就是 $O(n)$。

四、实验：亲手看见量级

本节不测时间，而是直接数"基本操作执行了多少次"。这样得到的表格与机器无关 —— 任何电脑上跑出来都是同一张表。

新建控制台项目，粘贴以下代码：

// 本节不比较时间，而是直接数「基本操作执行了多少次」。
// 这样得到的结论与机器无关：任何电脑上跑出来都是同一张表。

static long OpsConstant(int n) => 1;                       // O(1)

static long OpsLog(int n)                                  // O(log n)
{
    long ops = 0;
    for (int i = 1; i < n; i *= 2) ops++;                  // 1, 2, 4, 8, ... 成倍增长
    return ops;
}

static long OpsLinear(int n)                               // O(n)
{
    long ops = 0;
    for (int i = 0; i < n; i++) ops++;
    return ops;
}

static long OpsNLogN(int n)                                // O(n log n)
{
    long ops = 0;
    for (int i = 1; i < n; i *= 2)                         // 外层 log n 次
        for (int j = 0; j < n; j++) ops++;                 // 内层 n 次
    return ops;
}

static long OpsQuadratic(int n)                            // O(n^2)
{
    long ops = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) ops++;
    return ops;
}

Console.WriteLine($"{"n",8} | {"O(1)",10} | {"O(log n)",10} | {"O(n)",10} | {"O(n log n)",12} | {"O(n^2)",14}");
foreach (int n in new[] { 1_000, 2_000, 4_000, 8_000 })
{
    Console.WriteLine(
        $"{n,8} | {OpsConstant(n),10} | {OpsLog(n),10} | {OpsLinear(n),10} | " +
        $"{OpsNLogN(n),12} | {OpsQuadratic(n),14}");
}

// n 翻倍时操作次数涨几倍 —— 这才是大 O 真正描述的东西
Console.WriteLine();
Console.WriteLine("n 从 4000 涨到 8000（翻倍），操作次数涨几倍：");

double r1 = (double)OpsLog(8_000) / OpsLog(4_000);
double r2 = (double)OpsLinear(8_000) / OpsLinear(4_000);
double r3 = (double)OpsNLogN(8_000) / OpsNLogN(4_000);
double r4 = (double)OpsQuadratic(8_000) / OpsQuadratic(4_000);

Console.WriteLine($"  O(log n)   : {OpsLog(4_000),12} -> {OpsLog(8_000),12}   涨 {r1,5:F2} 倍");
Console.WriteLine($"  O(n)       : {OpsLinear(4_000),12} -> {OpsLinear(8_000),12}   涨 {r2,5:F2} 倍");
Console.WriteLine($"  O(n log n) : {OpsNLogN(4_000),12} -> {OpsNLogN(8_000),12}   涨 {r3,5:F2} 倍");
Console.WriteLine($"  O(n^2)     : {OpsQuadratic(4_000),12} -> {OpsQuadratic(8_000),12}   涨 {r4,5:F2} 倍");

实测输出（.NET 8 Release）：

       n |       O(1) |   O(log n) |       O(n) |   O(n log n) |         O(n^2)
    1000 |          1 |         10 |       1000 |        10000 |        1000000
    2000 |          1 |         11 |       2000 |        22000 |        4000000
    4000 |          1 |         12 |       4000 |        48000 |       16000000
    8000 |          1 |         13 |       8000 |       104000 |       64000000

n 从 4000 涨到 8000（翻倍），操作次数涨几倍：
  O(log n)   :           12 ->           13   涨  1.08 倍
  O(n)       :         4000 ->         8000   涨  2.00 倍
  O(n log n) :        48000 ->       104000   涨  2.17 倍
  O(n^2)     :     16000000 ->     64000000   涨  4.00 倍

看表的正确方式，是竖着看"涨了几倍"，而不是盯着绝对数字。

量级	4000 → 8000	涨了	与你预期是否一致
$O(\log n)$	12 → 13	1.08 倍	翻倍只多 1 次
$O(n)$	4,000 → 8,000	2.00 倍	翻倍就是 2 倍
$O(n \log n)$	48,000 → 104,000	2.17 倍	比 2 倍多一点
$O(n^2)$	16,000,000 → 64,000,000	4.00 倍	翻倍就是 4 倍

$n$ 翻倍时"涨几倍"这个数字，才是大 O 真正描述的东西。

顺带一个工程上的用处：如果不确定一段代码是什么量级，跑这个实验就行 —— 把 $n$ 翻倍，看操作次数涨几倍。涨 2 倍是线性，涨 4 倍是平方，涨得极快就是指数。

五、练习

练习 1.2.1（识别信号）不写公式，直接说出下面三段代码各是什么量级：

// (a)
for (int i = 0; i < n; i++) Console.WriteLine(i);

// (b)
for (int i = 0; i < n; i++)
    for (int k = 0; k < 10; k++) Console.WriteLine(i);

// (c)
int i = n;
while (i > 1) { Console.WriteLine(i); i /= 2; }

练习 1.2.2（化简）把下列表达式化简为大 O： (a) $5n + 200$ (b) $3n^2 + 100n + 7000$ (c) $\frac{n(n-1)}{2}$ (d) $2^{n} + n^{10}$

练习 1.2.3（反向推理）一个算法在 $n = 1000$ 时耗时 1 秒。如果它是 $O(n^2)$，那么 $n = 3000$ 时大约需要多久？（假设 $n$ 翻了 3 倍）

练习 1.2.4（易错题）下面这段代码，有人说"内层是常数 10 次，所以整体是 $O(n)$"，有人说"有两层循环，所以是 $O(n^2)$"。哪个对？为什么？

for (int i = 0; i < n; i++)
    for (int k = 0; k < 10; k++)
        sum += i * k;

练习 1.2.5（挑战）仓库里有 m 个商品、n 个订单。下面的代码是什么量级？如果已知 $m$ 恒为 50、$n$ 会增长到百万级，你会在工程上怎么处理它？

foreach (var product in products)        // m 个
    foreach (var order in orders)        // n 个
        if (order.ProductId == product.Id)
            order.ProductName = product.Name;

六、练习答案

1.2.1

(a) $O(n)$ —— 单层循环，i++ 逐步增长。
(b) $O(n)$ —— 内层固定 10 次，是一只常数。$n \times 10$ 去系数后仍是 $O(n)$。
(c) $O(\log n)$ —— i /= 2 成倍缩小。

1.2.2

(a) $O(n)$ —— 去掉系数 5 和常数项 200。
(b) $O(n^2)$ —— 只保留最高阶 $n^2$。注意 $100n$ 虽然系数很大，但 $n$ 一大就被 $n^2$ 完全盖过。
(c) $O(n^2)$ —— 展开得 $\frac{n^2}{2} - \frac{n}{2}$，去系数去低阶。
(d) $O(2^n)$ —— 指数增长远快于任何多项式。$n = 100$ 时 $2^{100} \approx 10^{30}$，而 $n^{10} = 10^{20}$。

1.2.3 $n$ 从 1000 涨到 3000，是 3 倍。平方量级意味着耗时涨 $3^2 = 9$ 倍。

所以约需 9 秒。

如果它是 $O(n)$，答案就是 3 秒；如果是 $O(n^3)$，就是 27 秒。只看一个数据点无法判断量级，必须比较两个不同的 $n$。 这正是上一节实验里要跑两档规模的原因。

1.2.4 第一个对，答案是 $O(n)$。

内层固定 10 次，是常数因子。总操作数 $= 10n$，去掉系数就是 $O(n)$。

"看到两层循环就是 $O(n^2)$"是一条口诀，不是规则。规则永远是把总次数算出来再化简。判断标准是内层次数随不随 $n$ 变化：随 $n$ 变化才是 $O(n^2)$，固定不变就只是系数。

1.2.5 量级是 $O(m \times n)$ —— 两个独立规模相乘，不要合并成 $O(n^2)$。

工程处理：既然 $m$ 恒为 50 而 $n$ 会涨到百万，$50 \times 10^6 = 5 \times 10^7$ 次比较虽然能跑，但每次都要遍历全部订单，代价偏高。更合理的做法是把 orders 按 ProductId 建一个哈希表索引，然后遍历 50 个商品去查表：

var ordersByProduct = new Dictionary<int, List<Order>>();
foreach (var order in orders)                    // O(n)：建索引，一次
{
    if (!ordersByProduct.TryGetValue(order.ProductId, out var list))
        ordersByProduct[order.ProductId] = list = new List<Order>();
    list.Add(order);
}

foreach (var product in products)                // O(m)：查索引
    if (ordersByProduct.TryGetValue(product.Id, out var list))
        foreach (var order in list)
            order.ProductName = product.Name;

总代价降到 $O(m + n)$。这是"用空间换时间"的第一个例子 —— 1.4 节会正式讨论这个权衡。

七、常见错误

误区	纠正
看到嵌套循环就写 $O(n^2)$	先把总次数算出来。内层固定次数（如 10 次）不随 $n$ 变化，只是系数，整体仍是 $O(n)$。
保留系数，写成 $O(2n)$	大 O 不写系数。$O(2n)$ 要写成 $O(n)$。（$O(2^n)$ 是指数，那是另一回事。）
把两个独立规模合成 $n$	$m$ 个商品 × $n$ 个订单是 $O(m \times n)$，不是 $O(n^2)$。除非题目明确说 $m = n$。
认为系数完全没意义	系数不影响量级判断，但影响实际速度。同为 $O(n \log n)$，归并排序比快排常数大，工程上仍可能选快排。
用大 O 预测精确耗时	大 O 说的是趋势。$n$ 小时常数项可能占主导，$O(n^2)$ 的实现甚至可能比 $O(n \log n)$ 更快。

八、本节总结

大 O 只保留增长方式，扔掉系数与低阶项：$\frac{n^2}{2} + n = O(n^2)$。
三条化简规则：去系数、留最高阶、加法取大乘法相乘。
常见量级从小到大：$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)$。
判断量级最可靠的方法是看"$n$ 翻倍时涨几倍"：1 倍内是常数/对数，2 倍是线性，4 倍是平方。
嵌套循环不必然是 $O(n^2)$；两个独立规模要写成 $O(m \times n)$。

下一节衔接：到目前为止我们说的"代价"都是一个数。但上一节的练习 1.1.6 已经暴露出一个问题：同一段代码，遇到"有重复"的数据立刻返回，遇到"没重复"的数据却要跑满全程。那么该说它是 $O(1)$ 还是 $O(n^2)$？下一节引入最好、最坏、平均三种情况，把这个矛盾说清楚。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "1.2",
  "title": "大 O 记法：描述增长，而不是秒数",
  "covered": [
    "系数不影响增长方式的论证",
    "大 O 的白话定义",
    "化简三规则（去系数/留最高阶/加法取大乘法相乘）",
    "常见量级表及其 n 翻倍时的倍率",
    "四类代码的复杂度分析（含两个独立规模 m×n）",
    "用操作计数而非时间做实验的方法"
  ],
  "unresolved": [
    "三种情况（最好/最坏/平均）留到 1.3",
    "空间复杂度与摊还代价留到 1.4",
    "哈希表索引的实际代价留到第 6 章"
  ],
  "canonical_terms": {
    "大 O 记法": "描述增长率上界的记号，记作 f(n) = O(g(n))",
    "渐进分析": "忽略常数与低阶项，只看增长趋势"
  },
  "symbols_units": {
    "O(f(n))": "增长率上界",
    "log n": "以 2 为底的对数",
    "m, n": "两个互相独立的输入规模"
  },
  "assumptions": [
    "读者已掌握 1.1 的输入规模与基本操作概念",
    "读者已会写双重循环与 foreach"
  ],
  "word_count_actual": 1180,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch01/Sec12/",
    "实测倍率与理论值逐项核对：1.08 / 2.00 / 2.17 / 4.00",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "next": "1.3 最好、最坏与平均：三个不同的答案"
}

1.2　大 O 记法：描述增长，而不是秒数