Chapter 01
复杂度与约束反推
起点页给了"把刷题变成认套路"的全局地图——这一章建立第一块、也是最先用到的地基：用复杂度给解法空间画边界。
本章你将建立的 schema
- 用 Big-O 描述增长量级，而非绝对运行时间。
- 看约束 n 的规模，反推出目标复杂度。
- 用复杂度提前排除不可行的套路。
- 权衡时间与空间——用空间换时间是高频手段。
§1.1Big-O 是什么
Big-O 描述运行时间随输入规模增长的量级，忽略常数与低阶项。
同一段代码在不同机器上跑出的秒数不同，无法用来比较算法优劣。Big-O 把"硬件、语言、编译器"这些噪声全部抹掉，只保留"输入翻倍时运行时间怎么变"这一条机器无关的本质。一个 O(n) 算法在慢机器上也终将打败快机器上的 O(n²) 算法——只要 n 足够大。
为何丢弃常数与低阶项
设一段代码的精确步数是 3n² + 5n + 100。当 n→∞，3n² 这一最高阶项完全主导：n=1000 时 3n²=3,000,000，而 5n+100=5100，后者占比不到 0.2%。低阶项与常数系数对增长趋势没有影响，因此 Big-O 把它丢掉，记作 O(n²)。
但工程与面试里常数有时要命。两次扫描数组（2n 次操作）与一次扫描（n 次）在 Big-O 下都是 O(n)，可实测前者慢一倍。当 n 巨大、或代码在热路径上反复调用时，这一倍的差距是真金白银。Big-O 告诉你"量级对不对"，常数告诉你"同量级里谁更快"——两者都要看。
实例：判断数组是否有重复元素
同一道题，两种量级。先看 O(n²) 的朴素双循环：对每个元素，向后比较所有其余元素。
def has_duplicate_n2(nums: list[int]) -> bool:
n = len(nums)
for i in range(n): # 外层：选定一个元素 nums[i]
for j in range(i + 1, n): # 内层：和它后面每个元素比较
if nums[i] == nums[j]: # 撞上相等 = 找到重复
return True
return False # 全部比完没撞上 = 无重复
# 比较次数约为 n*(n-1)/2，量级 O(n^2)
print(has_duplicate_n2([1, 2, 3, 1])) # True （1 出现两次）
print(has_duplicate_n2([1, 2, 3, 4])) # False （全不同）外层 × 内层两层嵌套循环各跑约 n 次，总比较次数与 n² 成正比，故复杂度 O(n²)。空间只用了几个变量，O(1)。
再看 O(n) 版本：用一个 set 记住"见过的元素"，每个新元素查一次集合即可。
def has_duplicate_n(nums: list[int]) -> bool:
seen: set[int] = set() # 记录已出现过的元素
for x in nums: # 只扫一遍数组
if x in seen: # set 查找平均 O(1)
return True # 这个值之前见过 = 重复
seen.add(x) # 没见过，记下来
return False # 扫完没撞上 = 无重复
# 扫描 n 次、每次 O(1) 查找，量级 O(n)；额外用 O(n) 空间存 set
print(has_duplicate_n([1, 2, 3, 1])) # True
print(has_duplicate_n([1, 2, 3, 4])) # False单次扫描循环执行 n 次，每次 in 与 add 在哈希集合上平均 O(1)，总复杂度 O(n)。代价是 O(n) 的额外空间——这正是"用空间换时间"，§1.4 再展开。
n=10000 时，两版的操作次数差多少个数量级？先估，再展开核对。
展开核对
O(n²) 版约 n²/2 = 10000²/2 = 5×10⁷ 次比较；O(n) 版约 10⁴ 次操作。两者相差约 5000 倍，即 3–4 个数量级。n 再翻 10 倍到 10⁵，差距扩大到约 5 万倍——这就是量级差异的可怕之处：它随 n 越拉越大。
§1.2复杂度阶梯
常见复杂度从快到慢排成一条阶梯，记住这条顺序，是后面"反推"的前提：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
O(1) 数组按下标取值、哈希表查找；O(log n) 有序数组二分查找；O(n) 遍历数组求和、单次扫描；O(n log n) 归并 / 快速排序；O(n²) 朴素双循环、冒泡排序；O(2ⁿ) 枚举集合的所有子集；O(n!) 枚举所有排列（如朴素求解旅行商）。
§1.3约束反推目标复杂度
这是本章的核心技能，也是整份教程判别链的第一步：题目给出的数据规模约束，直接框定了可行的复杂度，从而排除掉大半套路。
为什么能反推：按 10⁸ 次/秒估算
主流评测机一秒大约能执行 10⁸（一亿）次基本操作，多数题目时限 1–2 秒。把"可执行操作总数 ≈ 10⁸"当成预算，再代入复杂度公式解出 n 能取多大，反过来就得到"给定 n 时复杂度的上限"。例如 n=10⁶ 时，O(n²) 需要 10¹² 次操作 ≈ 超时一万倍，必然不可行；只有 O(n) 或 O(n log n) 落在预算内。
| 输入规模 n | 可接受复杂度 | 暗示的套路 |
|---|---|---|
| n ≤ 10–12 | O(n!) / O(2ⁿ) | 回溯、全排列 / 全枚举 |
| n ≤ 20 | O(2ⁿ) | 状态压缩、子集枚举 |
| n ≤ 500 | O(n³) | 三重循环、区间 DP |
| n ≤ 5000 | O(n²) | 二维 DP、朴素双循环 |
| n ≤ 10⁶ | O(n) / O(n log n) | 双指针、滑动窗口、排序、二分 |
| n ≥ 10⁸ | O(log n) / O(1) | 二分、数学公式直接算 |
读题第一眼看 n 的上界，立刻在表里定位行，候选套路就缩到一两类。这把"无从下手"变成"在两三个套路里挑"。
n≤10⁵ 的题，若硬上 O(n²) 解法，会发生什么？
展开核对
O(n²) = (10⁵)² = 10¹⁰ 次操作。按 10⁸ 次/秒算需约 100 秒，远超 1–2 秒时限，判定超时（TLE）。n≤10⁵ 落在表 1.1 的 O(n)/O(n log n) 行，正确做法是双指针、滑窗或先排序再二分。
§1.4空间复杂度与递归栈
空间复杂度描述额外内存随输入规模增长的量级；递归的隐藏开销是调用栈。
每次函数调用都会在调用栈上压入一个栈帧（保存局部变量、返回地址）。递归未返回时这些栈帧不会弹出，因此递归的空间开销是 O(最大递归深度)，即便函数体本身只用常数空间。Python 默认递归深度上限约 1000，且不做尾递归优化——再"尾"的递归也照样吃栈。深度过大会抛 RecursionError。
实例：递归求和的栈深度问题
import sys
def sum_recursive(nums: list[int], i: int = 0) -> int:
# 每深一层就压一个栈帧，递归深度 = len(nums)，空间 O(n)
if i == len(nums):
return 0
return nums[i] + sum_recursive(nums, i + 1)
def sum_iterative(nums: list[int]) -> int:
# 只用一个累加变量，无递归栈，空间 O(1)
total = 0
for x in nums:
total += x
return total
print(sum_iterative(list(range(100000)))) # 4999950000 一次跑通
try:
print(sum_recursive(list(range(100000)))) # 深度 10 万，远超默认上限
except RecursionError as e:
print("RecursionError:", e) # 触发栈溢出保护
# 若坚持用递归，需手动抬高上限（治标不治本，仍占 O(n) 栈空间）
sys.setrecursionlimit(200000)递归 vs 迭代两版时间都是 O(n)，但 sum_recursive 空间 O(n)（栈深度随 n 线性增长，n=10⁵ 直接 RecursionError），sum_iterative 空间 O(1)。深度可能很大时，优先改写成迭代。
§1.1 的去重题已经示范：哈希表（set / dict）额外吃 O(n) 空间，换来 O(1) 的平均查找，把 O(n²) 压到 O(n)。这是面试最高频的权衡手段——当时间预算（表 1.1）逼你降一个量级，第一反应就是"能不能拿空间换"。哈希表为何能 O(1) 查找、它的物理布局如何决定这一点，留到第 03 章展开。
§自测
- O(n) 与 O(n log n) 两段代码先后顺序执行，总复杂度是多少？
答案
O(n log n)。顺序执行取各段中量级最高者：O(n + n log n) = O(n log n)，低阶的 O(n) 被吸收。
- 一道题 n≤25，要求枚举所有子集（2ⁿ 个），可行吗？为什么？
答案
勉强可行但接近边界。2²⁵ ≈ 3.3×10⁷，落在 10⁸ 预算内。但 n≤30 时 2³⁰≈10⁹ 就超了——这类题目的 n 通常卡在 20 上下，正是子集枚举 / 状压的信号。
- Big-O 忽略常数，为什么工程里仍要关心常数？
答案
Big-O 只比较"量级"，同量级内常数决定实测快慢：两次扫描（2n）比一次扫描（n）慢一倍。在热路径、大 n 或卡常题里，这一倍是真实代价。Big-O 选对量级，常数决定同量级里谁更优。
- 一个递归函数体只用常数变量，它的空间复杂度一定是 O(1) 吗？
答案
不一定。还要加上调用栈：空间 = O(最大递归深度)。深度为 n 的递归即便函数体 O(1)，整体空间也是 O(n)。
n≤40 的子集和
给一个长度 n≤40 的整数数组与目标值 target，问是否存在某个子集的元素和恰好等于 target。朴素做法枚举全部 2ⁿ 个子集——n=40 时 2⁴⁰ ≈ 10¹²，按 10⁸ 次/秒约需 三小时，必然超时。这个 n 既大于纯枚举的上限，又小于 DP 友好的范围，怎么破？
提示
折半搜索（meet-in-the-middle）：把 40 个数拆成两半，各 20 个。左半枚举全部 2²⁰≈10⁶ 个子集和、存进有序数组或哈希；右半同样枚举 2²⁰ 个，对每个和 s 去左半里查是否存在 target − s。总量级从 O(2⁴⁰) 降到 O(2²⁰ × 20)≈10⁷，落回预算内。核心思路：指数被"对半砍"在指数位上，等于开平方。