1.4 复杂度判断
学习目标
学完这一节，你能：
- 说清楚"运行时间"和"增长趋势"的区别
- 为一个问题定义输入规模
n和基本操作 - 使用
O、Θ、Ω描述渐近界 - 用生活场景解释常见增长量级
- 从简单代码中推导常见时间复杂度
- 区分最好情况、最坏情况和平均情况
- 同时分析时间复杂度、空间复杂度和隐藏成本
快，是相对于规模说的
同一段代码，处理 100 条记录可能很快，处理 100 万条记录就可能拖垮系统。秒表只能告诉我们一次运行花了多久；复杂度要回答的是：
当输入规模变大时，算法需要的时间和内存怎样增长？
这里的"输入规模"通常记作 n。如果输入是一组商品，n 可以是商品数量；如果输入是一段文本，n 可以是字符数或词数；如果输入是两张表，可能需要同时记作 m 和 n。
复杂度判断的第一步不是写公式，而是说清楚：
n 表示什么？
我们把哪一种操作当作主要成本？
分析的是最好、最坏，还是平均情况？
除了时间，还需要多少额外内存？不先回答这些问题，O(n) 这样的结论就没有明确含义。
从秒表到代价模型
真实运行时间受很多因素影响：语言、硬件、缓存、网络、数据库、文件系统、输入分布都会改变秒数。复杂度分析不会假装这些因素不存在，而是先建立一个更稳定的数学模型。
我们把运行所需的主要步骤数写成 T(n)。
先看一个生活场景。
老师要统计全班午餐费用。班里有多少份订单，老师就要看多少张小票。30 份订单看 30 次，300 份订单看 300 次。人数变成 10 倍，主要工作也大约变成 10 倍。
这就是线性增长的直觉。
对应到代码：
def total_price(items):
total = 0
for item in items:
total += item.price
return total如果 n 是商品数量，循环体大约执行 n 次。total = 0 和 return total 只执行固定次数。于是可以写成：
T(n) = a·n + b这里 a 表示每次循环的大致成本，b 表示固定开销。复杂度关心的是 n 很大时主导增长的部分，所以这段代码的时间复杂度是 Θ(n)。
这就是代价模型：我们不追求每一纳秒都精确，而是抓住随输入规模增长的主导成本。
渐近记号：O、Θ、Ω
复杂度分析使用渐近记号描述"当 n 足够大时"的增长关系。
| 记号 | 读法 | 含义 |
|---|---|---|
O(g(n)) | 大 O | 最多按 g(n) 的量级增长，是渐近上界 |
Ω(g(n)) | 大 Omega | 至少按 g(n) 的量级增长，是渐近下界 |
Θ(g(n)) | 大 Theta | 上下界同阶，是渐近紧确界 |
初学时最常用的是 O 和 Θ。
如果一段代码的步骤数是：
T(n) = 3n² + 20n + 7当 n 很大时，n² 项会主导增长，常数 3 和低阶项 20n + 7 不改变增长量级。因此：
T(n) = Θ(n²)
T(n) = O(n²)
T(n) = Ω(n²)注意：O(n²) 只是说"不超过二次量级"，不一定是最紧的说法。一个 Θ(n) 的算法当然也可以说成 O(n²)，但这不够精确。教材中如果问"复杂度是多少"，通常希望你给出尽量紧的界，也就是 Θ(...) 或最贴近的 O(...)。
常见增长量级
下面这些量级会反复出现。现在不需要背算法名，先用熟悉场景建立直觉，再掌握它们的代码形状和规模后果。
| 量级 | 生活直觉 | 典型代码形状 | 当 n = 100,000 时的大致步骤数 |
|---|---|---|---|
O(1) | 不管队伍多长，只看第一个人的号码 | 只做固定次数操作 | 约 1 |
O(log n) | 猜 1 到 n 之间的数字，每次知道"大了"或"小了"，范围少一半 | 每一步把待处理范围缩小为原来的一部分 | 约 17 |
O(n) | 老师点名，每个学生都要叫到一次 | 看一遍所有输入 | 100,000 |
O(n log n) | 把名单分层整理：每层都处理全部人，总共有若干层 | 分层处理，每层总共看一遍输入 | 约 1,700,000 |
O(n²) | 全班同学两两握手，每个人都要和很多人配对 | 两两配对或双层遍历 | 10,000,000,000 |
O(2^n) | n 个套餐每个都可以选或不选，所有组合都试一遍 | 每个元素都有取或不取等分支 | 极大，通常不可接受 |
类比只能帮你建立感觉，不能代替推导。真正分析代码时，还是要回到输入规模、基本操作和执行次数。
但这些生活场景能帮你先抓住增长差异：
- 点名是
O(n)：多一个学生，多一次工作。 - 两两握手是
O(n²)：多一个学生，不只是多一次工作，而是多出他和所有人的配对。 - 猜数字每次砍掉一半范围，是
O(log n)：范围很大也不怕，因为减少得很快。 - 试所有选或不选的组合是
O(2^n)：每多一个候选，可能方案数就翻倍。
从 O(n²) 改到 O(n log n) 不是"优化了一点点"。当 n = 1,000,000 时，n² 是 10^12，而 n log₂ n 大约是 2 × 10^7，差距接近五万倍。
这也是为什么复杂度是一种工程判断力：它经常决定一个方案是能上线，还是只能在小样例里看起来可用。
一个数字感觉：握手为什么长得快
如果 5 个同学两两握手，握手次数是：
4 + 3 + 2 + 1 = 10如果 50 个同学两两握手，次数变成：
49 + 48 + ... + 1 = 1225人数只变成 10 倍，握手次数却变成 122.5 倍。原因是每增加一个人，他要和前面很多人都配一次。
这就是二次增长最该警惕的地方：它不是"多看几遍"这么简单，而是配对数量会迅速膨胀。
从代码中推导复杂度
复杂度不是猜出来的，而是从代码结构和操作成本推出来的。
顺序执行：相加后取主导项
def summarize(items):
total = 0
for item in items:
total += item.price
count = 0
for item in items:
if item.price > 100:
count += 1
return total, count两个循环各看一遍输入：
T(n) = n + n + 常数 = 2n + 常数 = Θ(n)顺序执行的几段代码，成本相加；最后保留增长最快的主导项。
嵌套循环：看内层总共执行多少次
刚才的"两两握手"可以直接翻译成代码：把每一对编号拿出来检查一次。
def count_pairs(nums):
count = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == 100:
count += 1
return count外层第 0 次时，内层执行 n - 1 次；外层第 1 次时，内层执行 n - 2 次；一直到最后。
所以比较次数是：
(n - 1) + (n - 2) + ... + 1
= n(n - 1) / 2
= (n² - n) / 2
= Θ(n²)这段代码不是因为"有两层循环"才机械地等于 Θ(n²)，而是因为内层总执行次数形成了二次增长。这个区别很重要：有些双层循环不是二次，有些单层循环也可能隐藏更高成本。
每次缩小一半：对数量级
再看"猜数字"。
假设答案在 1 到 1000 之间。你每次问中间值，然后别人告诉你答案更大还是更小。第一次以后，范围最多只剩 500 个；第二次最多 250 个；第三次最多 125 个。
每一步都不是只少一个候选，而是砍掉一大半。这就是对数增长的直觉。
def halve_until_one(n):
steps = 0
while n > 1:
n = n // 2
steps += 1
return steps第 k 次循环后，规模大约变成：
n / 2^k循环停止时需要：
n / 2^k <= 1也就是：
2^k >= n所以：
k >= log₂ n循环次数是 Θ(log n)。这里的 log 底数不影响大 O 量级，因为不同底数之间只差一个常数倍。
最好、最坏和平均
复杂度必须说明分析的是哪一种情况。
看下面这段代码：
def contains(items, target):
for item in items:
if item == target:
return True
return False如果目标正好在第一个位置，循环一次就结束，这是最好情况 Θ(1)。
如果目标不存在，或者在最后一个位置，就要看完整个列表，这是最坏情况 Θ(n)。
如果目标等概率出现在任意位置，平均大约看半个列表，仍然是 Θ(n)，因为 n/2 和 n 只差常数倍。
除非题目特别说明输入分布，教材中默认优先分析最坏情况。最坏情况给的是一种保守保证：无论输入怎么来，成本不会超过这个量级。
空间复杂度
时间复杂度问：
需要多少步骤？
空间复杂度问：
除了输入本身，还需要多少额外内存？
例如查找重复编号，可以两两比较：
def has_duplicate_slow(ids):
n = len(ids)
for i in range(n):
for j in range(i + 1, n):
if ids[i] == ids[j]:
return True
return False这段代码最坏时间是 Θ(n²)，但额外空间是 Θ(1)，因为它只用了少量变量。
也可以边扫描边记录已经见过的编号：
def has_duplicate_fast(ids):
seen = set()
for x in ids:
if x in seen:
return True
seen.add(x)
return False这里的 set() 可以先理解成"见过的编号记录表"。在常见实现和通常输入下，查询和加入记录表可以近似看作常数时间；它的内部原理会在数据结构章节再讲。
这段代码通常是 Θ(n) 时间，但需要保存最多 n 个编号，所以额外空间是 Θ(n)。
这就是常见取舍：用更多内存，换更少时间。
隐藏成本：一行不一定是一步
复杂度审查最容易犯的错误，是只数肉眼可见的循环。
生活中也有类似情况。班长整理报名名单时，每来一个新名字，都要先翻一遍已经写好的名单，确认是不是重复报名。表面上只是"处理一个新名字"，实际里面藏着一次查找；名单越长，翻得越久。
def unique_names(names):
result = []
for name in names:
if name not in result:
result.append(name)
return result表面上只有一层循环。但 name not in result 需要在 result 里从前往后找。随着 result 变长，这一行会越来越贵。
最坏情况下，它的检查次数接近：
0 + 1 + 2 + ... + (n - 1) = n(n - 1) / 2 = Θ(n²)类似地，下面这些操作都不能默认当成一步：
- 在列表里查找某个值
- 在列表开头插入或删除
- 对数据排序
- 调用一个内部又遍历输入的函数
- 访问数据库、文件或网络
专业的复杂度分析要追问每一行背后的真实工作，而不是只看缩进层级。
复杂度预算
复杂度判断最终要落到约束上。
输入规模：最多 100,000 条记录
时间要求：1 秒内返回
内存要求：不超过 512 MB
结果要求：必须精确在这个规模下，可以先做粗估：
| 复杂度 | 大致工作量 | 初步判断 |
|---|---|---|
Θ(n) | 100,000 | 通常可继续考虑 |
Θ(n log n) | 约 1,700,000 | 通常可继续考虑 |
Θ(n²) | 10,000,000,000 | 通常需要警惕 |
Θ(2^n) | 极大 | 通常不可接受 |
这张表不是测速结果。真实性能还要测量，尤其是有数据库、网络、文件和大对象时。
但复杂度预算能帮助你迅速拒绝明显不合适的方向。数据规模是 100,000，还要求 1 秒返回，如果方案需要两两比较所有记录，它很可能在设计层面就不合格。
可以把它想成学校活动安排：
- 点名 100,000 人已经很累，但至少是"一个接一个"。
- 让 100,000 人两两确认是否认识，配对数大约是 5,000,000,000 对。
这两个任务都和 100,000 人有关，但完全不是同一个规模的工作。复杂度分析训练的，就是在写代码前先看出这种差别。
复杂度不是唯一标准
复杂度很重要，但它不是唯一标准。
- 小规模数据：当
n很小时，简单的Θ(n²)代码可能比复杂的Θ(n log n)代码更快。 - 常数成本：同样是
Θ(n)，一次内存访问和一次网络请求不是同一个成本。 - 输入分布：最坏情况很少发生时，平均表现也值得测量，但前提是你能说明输入分布。
- 实现细节：同一复杂度的两个实现，缓存友好程度、对象分配次数、库函数成本可能差很多。
因此，复杂度分析不是替代实验，而是指导实验：它告诉你哪些方案值得测，哪些方案大概率不值得继续投入。
复杂度审查清单
分析一段代码时，按下面顺序检查：
n是什么？是否还需要m、k等其他规模参数？- 基本操作是什么？比较、访问、插入、函数调用，还是外部 I/O？
- 顺序执行的成本如何相加？
- 循环总共执行多少次？不要只数循环层数。
- 有没有隐藏成本，例如查找、排序、删除、数据库访问？
- 分析的是最好、最坏还是平均情况？
- 额外空间是多少？是否用内存换了时间？
- 在目标规模和时间、内存约束下是否可接受？
这份清单比单独记一个 O(...) 更重要。复杂度判断的价值，不在于背出符号，而在于能解释符号为什么成立。
本节要点
- 复杂度描述输入规模增长时的时间和空间增长趋势，不等于一次运行的秒数。
O是上界，Ω是下界，Θ是紧确界；回答复杂度时应尽量给出紧的量级。- 点名、两两握手、猜数字、试所有组合等生活场景可以帮助建立增长量级直觉，但最终仍要回到执行次数推导。
- 顺序代码成本相加，嵌套循环要计算内层总执行次数，每次缩小固定比例通常产生对数量级。
- 最好、最坏和平均情况可能不同；除非特别说明，教材通常优先分析最坏情况。
- 一行代码可能隐藏扫描、排序、插入、删除或外部访问成本。
- 复杂度分析和实际测速互相配合：先用模型排除明显不合适的方案，再用实验确认真实表现。
课堂练习
练习 1：推导配对检查的复杂度
先回答生活问题：一个班有 n 位同学，如果每两位同学都要互相握手一次，总共要握手多少次？
再阅读代码，不运行，写出比较次数的求和式，并化简到渐近量级。
def count_pairs(nums):
count = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == 100:
count += 1
return count回答：
n表示什么？- 握手问题和这段代码里的哪一部分对应？
- 内层循环总共执行多少次？
- 时间复杂度的紧确界是什么？
- 额外空间复杂度是什么？
练习 2：识别隐藏成本
下面代码表面上只有一层循环：
def remove_duplicates(names):
result = []
for name in names:
if name not in result:
result.append(name)
return result回答：
- 哪一行隐藏了额外工作？
- 最坏情况下，隐藏工作形成了什么求和式？
- 时间复杂度为什么不是
Θ(n)？ - 如果改用一个"见过的名字记录表"，时间和空间会怎样变化？
练习 3：分析折半循环
先想一个猜数字游戏：答案在 1 到 n 之间，每次都能排除大约一半范围。然后阅读代码，说明它为什么是对数量级。
def count_halves(n):
count = 0
while n > 1:
n = n // 2
count += 1
return count回答：
- 第
k次循环后，n大约变成多少？ - 循环停止条件如何写成不等式？
- 为什么循环次数是
Θ(log n)？
练习 4：复杂度预算
某功能需要处理最多 200,000 条记录，要求 10 秒内完成，机器内存有限。
请比较下面四类方案是否值得继续考虑：
| 方案 | 时间复杂度 | 额外空间 |
|---|---|---|
| A | Θ(n) | Θ(n) |
| B | Θ(n log n) | Θ(1) |
| C | Θ(n²) | Θ(1) |
| D | Θ(2^n) | Θ(n) |
你的答案必须说明：
- 哪些方案可以优先尝试？
- 哪些方案需要警惕或拒绝？
- 时间和空间之间有什么取舍？
课后测验
📝 课后测验
上一节：1.3 如何验证正确性
下一节：1.5 建模