第1章：算法复杂度分析
Vol 2：算法森林探险 · 第1站：复杂度瞭望台
你在哪
你告别了变量村，背着行囊走进了村后的算法森林。老陈师傅递给你一张泛黄的地图——上面画着一条蜿蜒的路和一行字："这是复杂度分析。它会告诉你哪条路走得通、哪条路会困死你。"
后山小道走到尽头，你眼前是一座陡峭的瞭望台。
上山的路还有好几条——有人背着满背包的试炼题册，有人手里捏着林间石碑上的冒险者名次截图，有人满头大汗地翻着前人笔记问什么叫 O(n²)。你跟他们不同：你背着一个空包，兜里只有一支笔，和一个清醒的早晨。
这个瞭望台叫"复杂度分析"。它不教你写代码。它教你——在还不写代码的时候，就知道一段代码的命有多长。
你的任务
本章分层
- 必读：大 O 记号的含义与简化规则（只保留最高阶、丢弃常数）；常见复杂度 O(1)/O(log n)/O(n)/O(n log n)/O(n²)/O(2ⁿ) 图谱及其实际增长差距；最简单递归的时间与空间复杂度分析（二分查找和 Fibonacci 的递归树）
- 选读：Ω 和 Θ 符号的含义（知道存在即可，日常工作用不到）；递归的空间复杂度陷阱
- 深水区：更复杂的递归式分析（分治递归的直观理解）
本章不会要求你掌握
- Master Theorem 的公式化推导和三种情况判断
- 精确的复杂度计算（我们只关心增长趋势）
- Ω/Θ 的各种超集/子集关系
学完这一章，你要能做到以下三件事：
- 给任意一段代码写出大 O 记号——不是猜，是推。
- 一眼分出 O(1)、O(log n)、O(n)、O(n log n)、O(n²)
- 理解递归函数的时间与空间复杂度（二分查找和 Fibonacci 级别即可）
如果能做到，后山的路，你基本不会走错。
遭遇战：林间石碑上的数鸡腿谜题
你遇到的第一个对手，是一道刻在石板上的谜题。
你沿着林间小径走到一片空地。空地中央立着一块石碑，上面刻着一行字和一个奇怪的规则：
"林间驿站有 N 份干粮需要配对发放，每个冒险者领一份主粮和一份配粮，但编号相邻的两份（比如 1 号和 2 号）不能同时发放。请告诉驿站长老——最多能同时发出几份？"
你在石碑旁翻到了前人的冒险者笔记，上面写着最直觉的解法：
# 暴力版：两两检查 → O(n²)
def max_meals(orders):
n = len(orders)
count = 0
for i in range(n):
for j in range(i + 1, n):
if abs(orders[i] - orders[j]) != 1:
count += 1
return count这个跑法叫"两两对联检查"——能跑，但林子里的干粮只有 10 份的时候还行，有 1000 份的时候你的处理速度已经远远落后于冒险者排队的长度了。
这就尴尬了。 你的算法是 O(n²)，冒险者在 O(n) 地排队取粮。速度不匹配，抽象地看是"复杂度"，现实中就是"驿站后厨爆炸"。
为什么 O(n²) 会出问题？
因为 n 变成 1000 时，n² = 1,000,000，而 n 只有 1000。差三个数量级。CPU 可以一秒跑几亿次运算——跑一次线性扫描绰绰有余，但跑一百万次双层遍历 + 重复计数，就开始喘了。
更可怕的是增长曲线。n 从 1000 到 2000 只翻了一倍，n² 从 1,000,000 暴涨到 4,000,000——翻了四倍。这就是平方增长的真实含义：规模每翻一倍，工作量翻四倍。
而 O(n) 的算法呢？2000 的数据只比 1000 多跑一倍。线性和平方之间的距离，不是量变，是质变。
** Java 差异：** Java 没有原生
for i in range(n)这种迭代风格。你写for (int i = 0; i < n; i++)，但时间复杂度分析的结果完全一样——语言差异不会让 O(n²) 变成 O(n)。运行时差异主要体现在 JIT 编译后的热点代码优化上，但那属于常数因子的范畴。
** C++ 差异：** C++ 中如果你开
std::vector<int>传参却不传引用（vector<int> orders），实际上每一层递归或函数调用都会深拷贝整个数组——O(n) 的拷贝代价可能会淹没你的 O(n²) 双循环分析。传引用是 C++ 程序员的本能，但在复杂度分析里尤其致命。
常见陷阱：复杂度分析的三个标尺
1. 大 O —— 上界（最坏情况）
大 O 说的是"这段代码跑完，绝对不会比这个更差"。
# O(n) — 单次遍历
def find_max(arr):
max_val = arr[0]
for x in arr: # 这一行跑 n 次
if x > max_val:
max_val = x
return max_val规则很简单： 只看最高阶，去掉常数。
3n + 5→ O(n)n² + 100n + 1→ O(n²)log₂(n) + 1000→ O(log n)
为什么常数可以不管？因为当 n 很大的时候，常数不重要。
n = 10⁶
n² = 10¹² ← 现代 CPU 也得跑几百毫秒
n = 10⁶ ← 几乎实时
log n ≈ 20 ← 眨眼之间2. 大 Ω —— 下界（最好情况）
大 Ω 说"最少也要跑这么多"。比如在已排序数组里做线性查找，最好情况是第一个元素就命中——Ω(1)。但通常我们不怎么用大 Ω，因为它太乐观了，不给你兜底。
3. 大 Θ —— 紧界（确定边界）
当上界和下界一样时——也就是无论最好最坏都是这个复杂度——就用大 Θ。
# Θ(n) — 不管数组多乱，每次必跑 n 次
def sum_all(arr):
total = 0
for x in arr:
total += x
return total最好、最坏和平均
def linear_search(arr, target):
for i, x in enumerate(arr):
if x == target:
return i
return -1| 复杂度 | 场景 | |
|---|---|---|
| 最好情况 | O(1) | 第一个就是 |
| 最坏情况 | O(n) | 最后一个或没有 |
| 平均情况 | O(n) | 假设等概率分布 |
常见复杂度图谱
让我们把每种复杂度和一个真实生活场景绑定，这样你永远不会忘：
先看一个区分度极高的考题：你能在三秒内说出下面两段代码的时间复杂度差异吗？
# 代码 A
def sum_squares(n):
total = 0
for i in range(n):
for j in range(n):
total += i * j
return total
# 代码 B
def sum_logs(n):
total = 0
for i in range(n):
j = n
while j > 1:
total += j
j //= 2
return total答案： 代码 A 是 O(n²)，代码 B 是 O(n log n)。区别在于内层循环的边界——一个是线性增长（两次 n），一个是对数衰减（log₂n 次）。
下面这张表给了你一个永不混淆的记忆锚点：
| 复杂度 | 隐喻 | 代码特征 |
|---|---|---|
| O(1) | 翻开书本第 100 页——页码就是坐标 | 直接索引、简单算术运算 |
| O(log n) | 翻字典：翻到中间，比大小，再翻一半 | 每次砍掉一半问题空间 |
| O(n) | 全班点名：一个个人名念过去 | 单层 for 循环 |
| O(n log n) | 整理一摞试卷：分成小堆，每堆排好，再合并 | 分治 + 合并（归并排序、快速排序） |
| O(n²) | 全班同学两两握手：每个人都跟其他所有人握一次 | 双层嵌套 for 循环 |
| O(2ⁿ) | 每层台阶都有两条岔路，走完 n 层发现走了 2ⁿ 条路 | 无 memo 的双路递归 |
| O(n!) | 给十个人安排宴会座次：所有排列都试一遍 | 全排列穷举 |
def demo_complexities(n):
# O(1) — 常数
steps = n * 2 # 一次乘法
# O(log n) — 对数
count = 0
while n > 1:
n //= 2
count += 1
print(f"O(log n): 层数 = {count}")
# 输出（n=1024）: O(log n): 层数 = 10
# O(n) — 线性
for i in range(n):
_ = i ** 2
# O(n log n) — 线性对数
# 等价于 n 次对数操作
for i in range(n):
j = n
while j > 1:
j //= 2
# O(n²) — 平方
for i in range(n):
for j in range(n):
_ = i + j
# O(2ⁿ) — 指数
# 递归 fib(n) 无 memo → 见后文O(1) 常数 ← 数组索引、哈希表查找
O(log n) 对数 ← 二分查找、平衡树
O(n) 线性 ← 单次遍历
O(n log n) 线性对数 ← 快速排序、归并排序
O(n²) 平方 ← 双层循环、冒泡排序
O(2ⁿ) 指数 ← 递归穷举（如斐波那契未优化）
O(n!) 阶乘 ← 全排列穷举大小关系（n 很大时）：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
** Java 差异：** Java 的
ArrayList.contains()是 O(n) 扫描。HashSet.contains()是 O(1)——但对基础类型和引用类型的 hashCode 实现非常敏感。如果你的hashCode()写得烂（比如每次都返回同一个值），它会退化成 O(n)。
** C++ 差异：**
std::vector的push_back摊销 O(1)，std::map的find是 O(log n)（红黑树），std::unordered_map平均 O(1) 最坏 O(n)（哈希冲突）。这些都是在生产中经常踩的坑。
🔄 递归复杂度与 Master Theorem
递归算法的复杂度不能直接用循环算——你得"数递归树有几层、每层有几个节点"。
案例：二分查找
def binary_search(arr, left, right, target):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search(arr, mid + 1, right, target)
else:
return binary_search(arr, left, mid - 1, target)递归式： T(n) = T(n/2) + O(1)
每层把问题规模减半，然后做 O(1) 的比较。层数 = log₂n，所以 T(n) = O(log n)。
案例：糟糕的斐波那契
# 千万别在生产里写这个
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)递归式： T(n) = T(n-1) + T(n-2) + O(1)
这棵树每层节点数翻倍——两叉向下。深度 n，节点数约 2ⁿ。所以 T(n) = O(2ⁿ)。n=50 时你的电脑会卡成幻灯片的程度。
怎么救你？ 加记忆化（memoization）——把算过的结果存下来，别重复算。
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)加了 lru_cache 之后，每个 n 只算一次 → O(n)。
递归的空间复杂度陷阱
很多人只分析时间，忘了空间。递归的空间复杂度 = 递归栈的最大深度。
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)这个递归深度 = n（从 n 一路降到 1）。每层存一个栈帧。空间复杂度 O(n)。
而它的迭代版：
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i
return result空间复杂度 O(1)——我们就用了两个变量。
递归的代价： 如果你的机器栈空间有限（比如嵌入式系统只有 64KB 栈），深度 1000 的递归直接爆栈。不是"慢了就优化"的问题——是"程序根本跑不完"的问题。
这个教训在面试里也经常出现："这个递归版空间复杂度是多少？"如果你答 O(1)，面试官会微笑。答案是 O(n)，因为每一层递归调用都在栈上留下了帧。
以后需要时再回来看：Master Theorem
本节是可选扩展内容。 初学者完全可以跳过，以后再回来看。主线只需要理解上述二分查找和 Fibonacci 的递归树分析就够了。
当你遇到这样的递归式时，有一种通用工具叫 Master Theorem：
T(n) = a * T(n/b) + f(n)其中 a ≥ 1, b > 1，f(n) 是每一层合并或额外工作的复杂度。核心逻辑：把 n^log_b(a)（叶子层的工作量）和 f(n)（合并层的工作量）比一比。
| 情况 | 条件 | 结果 |
|---|---|---|
| 叶子主导（Case 1） | f(n) 比 n^log_b(a) 增长慢 | T(n) = Θ(n^log_b(a)) |
| 各层均衡（Case 2） | f(n) ≈ n^log_b(a) | T(n) = Θ(n^log_b(a) · log n) |
| 合并主导（Case 3） | f(n) 比 n^log_b(a) 增长快 | T(n) = Θ(f(n)) |
背不住也没关系。 你只需要记住一条心法：谁大听谁的，相等乘 log。
我们实操一把：
| 递归式 | a | b | log_b(a) | f(n) | 结果 |
|---|---|---|---|---|---|
| T(n) = T(n/2) + O(1) | 1 | 2 | 0 | O(1) | Θ(log n) |
| T(n) = 2T(n/2) + n | 2 | 2 | 1 | n | Θ(n log n) |
| T(n) = 4T(n/2) + n | 4 | 2 | 2 | n | Θ(n²) |
| T(n) = 2T(n/2) + n² | 2 | 2 | 1 | n² | Θ(n²) |
通关挑战
试试这几个，自己推一遍。（答案在最后）
- 以下代码的时间复杂度是什么？
def mystery(arr):
n = len(arr)
result = 0
for i in range(n):
for j in range(i, n):
result += arr[i] + arr[j]
return result- 以下递归函数的时间复杂度是多少？（提示：画递归树）
def binary_search(arr, left, right, target):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search(arr, mid + 1, right, target)
else:
return binary_search(arr, left, mid - 1, target)- 以下代码的空间复杂度呢？
def duplicate_matrix(n):
# 返回 n×n 矩阵
return [[0] * n for _ in range(n)]👆 参考答案（先自己推）
1. 内层从 i 到 n，总共执行 n + (n-1) + ... + 1 = n(n+1)/2 → O(n²)
2. 每次递归规模减半，每层只做 O(1) 工作。递归树深度 = log₂n。总复杂度 = O(log n)
3. n×n 矩阵需要 n² 个元素的空间 → O(n²)
验收标准
读完本章后，你能：
- [ ] 给任意嵌套循环写大 O（只看最高阶，扔掉常数）
- [ ] 区分 O(log n)、O(n)、O(n log n)、O(n²)
- [ ] 理解递归复杂度（二分查找 O(log n)、无 memo 的 Fibonacci O(2ⁿ)）
- [ ] 理解为什么 O(2ⁿ) 和 O(n²) 的实际差距是指数级的
- [ ] 知道分析空间复杂度时不只看变量的数量，还要看递归栈的深度和额外数据结构的大小
- [ ] （可选）知道存在 Master Theorem 这类工具，以后需要时再回来看
常见卡点
| 卡点 | 真相 |
|---|---|
| "常数不重要？那我到处塞常数" | 常数在不改变增长趋势时才不重要。1000n 还是 O(n)，但你会用 1000 倍的原因吗？ |
| "递归就是 O(2ⁿ)" | 错。只有像 fib 那样两叉全分裂才是。二分查找是单路递归，O(log n) |
| "空间复杂度只算变量" | 不算递归栈是大坑。深度 n 的递归，空间 O(n) |
| "O(log n) 的底数是多少？" | 不重要。 log₂n、log₁₀n、ln n 只差一个常数因子。所以一律叫 O(log n) |
现在不需要理解
这一章不考你：
- 平摊分析（Amortized Analysis） —— 动态数组的摊销 O(1) 后面在数组章节讲
- P vs NP —— 那是另一个世界的故事
- 精确复杂度 —— 我们只关心增长趋势，不需要算出精确的运算步数
- Ω 和 Θ 的各种超集/子集关系——大 O 是你面试和工作中 95% 时候用的东西。Ω 和 Θ 是锦上添花，不是雪中送炭
旅人笔记
- 大 O 是面试的面包和黄油——80% 的算法题只用到 O(n) 和 O(n²) 的判断，别在这里翻车。你只要能流利地说出"这个是 O(n²)，因为这个双重循环"，面试官就知道你基本功过关。
- 递归 + memo = 动态规划——如果你注意到 fib(n-1)+fib(n-2) 的重复计算，就已经踩在 DP 的门口了。动态规划的本质，就是"识别重复子问题，然后别算两遍"。
- "先写出对的，再优化快的"——正确性压倒一切。微优化是最后 10% 的事。一个面试者曾花了 15 分钟在 O(n log n) 的基础上抠常数，结果写出来的代码跑出 bug 了——得不偿失。
- 面试时说出"这个解法是 O(n²)，但用哈希表可以降到 O(n)"，比直接给出最优解更值钱——你证明了你能识别复杂度瓶颈，而不是恰好背过这个题。
- 空间换时间是永恒的交易——用缓存（哈希表）把 O(2ⁿ) 降到 O(n)，本质上是用额外 O(n) 的内存换指数级的时间节约。这种 trade-off 会在整本书里反复出现。
→ 下一站预告
第2章：数组与链表
现在你会算"这段代码跑多快"了。下一站，我们来看最基础也最实用的两种数据结构——数组和链表。你将亲手感受连续内存和散落内存的差距，学会在什么场景下选谁。
准备好了吗？往下翻。