复杂度分析

比较两种算法时，不能只看「我电脑上跑了 3 毫秒」。机器快慢、数据形态、是否命中缓存都会影响实测。工程里更常用的是：用数量级描述——输入规模变大时，耗时和额外内存怎么涨。

这就是时间复杂度和空间复杂度，通常用大 O 记号（Big-O）表示。

本文解决什么问题

• 什么是输入规模 $n$
• 大 O 到底在忽略什么、保留什么
• 如何从代码估算复杂度
• 最好 / 平均 / 最坏，以及空间复杂度
• 开发时怎么用这些结论做选型

输入规模 n

把「问题有多大」抽象成一个（或几个）整数。例如：

• 数组 / 链表长度是 $n$
• 图有 $n$ 个顶点、$m$ 条边（常同时用两个参数）
• 字符串长度是 $n$，模式串长度是 $m$

复杂度写成这些参数的函数，例如 $O(n)$、$O(n^2)$、$O(n + m)$。

大 O 在说什么

大 O 描述的是增长趋势的上界（常用来写最坏情况），并且：

• 忽略常数系数：$3n$ 与 $n$ 都写作 $O(n)$
• 只保留增长最快的项：$n^2 + 100n + 5$ 写作 $O(n^2)$

它回答的是：「$n$ 很大时，大概按什么曲线变慢」，不是精确毫秒数。

和其他记号的关系（了解即可）

• $\Theta(f)$：紧确界（上下都按 $f$ 涨）
• $\Omega(f)$：下界
  教材和面试里最常写的是 大 O。初学先把大 O 用熟即可。

常见时间复杂度（从快到慢）

复杂度	名字	直觉例子
$O(1)$	常数	读数组下标 a[i]、栈的 push/pop（摊还意义下）
$O(\log n)$	对数	有序数组二分查找
$O(n)$	线性	扫一遍数组
$O(n \log n)$	线性对数	高效排序（归并；快速排序平均）
$O(n^2)$	平方	双重循环两两比较
$O(n^3)$	立方	三重循环；某些 Floyd 全源最短路实现
$O(2^n)$	指数	朴素子集枚举、朴素斐波那契递归
$O(n!)$	阶乘	全排列暴力枚举

提示

对数通常默认以 2 为底。$n = 10^6$ 时，$\log_2 n$ 大约只有 20，所以 $O(\log n)$ 非常「香」。
粗算：$n \approx 10^7$ 量级时，$O(n)$～$O(n \log n)$ 在一般 OJ / 业务热路径里较常见；$O(n^2)$ 对 $n = 10^6$ 通常不可接受。

怎么估一段代码的复杂度

核心看：循环跑多少次、递归树有多大。

/* O(1) */
int x = a[0];

/* O(n) */
for (int i = 0; i < n; i++) {
    sum += a[i];
}

/* O(n^2) */
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        /* ... */
    }
}

/* 仍是 O(n^2) 量级：内层次数随 i 变化 */
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        /* 总次数约 n + (n-1) + ... + 1 = n(n+1)/2 */
    }
}

多段代码取「更慢的那段」

/* 先 O(n) 再 O(n log n) → 整体 O(n log n) */
sort_array(a, n);     /* 假设 O(n log n) */
scan_once(a, n);      /* O(n) */

顺序执行时，总复杂度由增长最快的部分主导（同类项可合并系数后仍归入同一大 O）。

递归怎么估

• 每次规模减 1，且只有一处递归：常见 $O(n)$（如线性递归求阶乘）
• 每次分成两个 $n/2$，合并 $O(n)$：常见 $O(n \log n)$（归并）
• 树形递归且大量重复子问题：可能到指数（朴素斐波那契）

更系统的主定理放到分治章节用；这里先会「画递归树 / 数递归次数」即可。

最好 / 平均 / 最坏

同一算法在不同输入上可能差很多：

情形	含义	例子
最好	运气最好	顺序查找时目标在第一个
最坏	运气最差	目标在最后或不存在；快排遇到已有序且 pivot 选得差
平均	某种输入分布下的期望	需要约定分布，分析更细

教材和面试里若没特别说明，时间复杂度常指最坏情况。工程上还会关心平均与「是否容易撞上最坏」。

空间复杂度

看额外占用了多少与 $n$ 相关的内存（通常不计输入本身）：

情况	额外空间
只用几个临时变量	$O(1)$
再开一个长度 $n$ 的数组	$O(n)$
递归深度为 $d$	调用栈约 $O(d)$

「原地算法」通常指额外空间是 $O(1)$ 量级（不计输入与递归栈时要看教材约定；写文章时最好说清楚是否含递归栈）。

/* 额外 O(1)（不计输入 a） */
void swap_ends(int *a, int n) {
    int t = a[0];
    a[0] = a[n - 1];
    a[n - 1] = t;
}

/* 额外 O(n) */
void copy_array(const int *src, int *dst, int n) {
    for (int i = 0; i < n; i++) dst[i] = src[i];
}

摊还分析（先建立直觉）

有时单次操作最坏很贵，但一连串操作平均很便宜。例如动态数组扩容：

• 某一次 push 可能触发扩容，拷贝 $n$ 个元素 → 单次看起来 $O(n)$
• 但扩容次数很少，均摊到每次 push 仍是 $O(1)$

以后看到 std::vector::push_back 的「摊还 $O(1)$」，指的就是这类结论。

实测和复杂度的关系

复杂度不能替代 profiling，但能帮你排除明显不合格的方案：

1. 先保证正确，再谈优化
2. $n$ 很小时，$O(n^2)$ 也可能完全够用
3. $n$ 到百万级时，优先避开热路径上的 $O(n^2)$
4. 常数、缓存、分支预测会影响实测；大 O 相同的两个实现，仍可能差几倍

常见误区

• 把「循环写了两层」就一律当成 $O(n^2)$：若内层与 $n$ 无关（固定 3 次），仍是 $O(n)$
• 忽略递归栈或隐藏的拷贝（如每次传入大对象）
• 只优化了非热点路径，整体体感没变化

初学者怎么用复杂度

1. 对每个关键操作写下：最好 / 最坏（至少最坏）
2. 用业务里的 $n$ 粗算能否接受
3. 结构选型往往就是在换复杂度（例如用哈希表换查找时间，用空间换时间）
4. 保留一个正确的慢算法，给快算法做对照

小结

• 时间复杂度：耗时如何随规模增长
• 空间复杂度：额外内存如何随规模增长
• 大 O 是数量级工具，用来比较和选型，不是墙钟时间

下一篇建立 递归思想，很多树、图与分治算法都靠它表达。