算法-复杂度分析
一句话概括
复杂度分析(Complexity Analysis) 是一套「不运行代码就能预估资源消耗」的数学工具。它回答两个问题:这段代码随输入规模 变大,时间会涨多快?内存会涨多快?
本篇覆盖:大 / / 的形式化定义、常见增长曲线与具体耗时估算、最好/最坏/平均情况、均摊分析(聚合法)、递归分析三件套(递归树、代入法、主定理)、空间复杂度与递归栈、算法复杂度速查表、P 与 NP、工程中的性能估算方法。
这是全库最重要的基础篇之一——后面每一篇算法笔记的结论都建立在这里的记号之上。
是什么
三种渐进记号
设 、 是定义在正整数上的函数(通常是算法的「基本操作次数」)。
形式化定义
大 (渐进上界):存在常数 与 ,使得对所有 都有 。记作
大 (渐进下界):存在常数 与 ,使得对所有 都有 。记作
大 (渐进紧确界): 且 ,即存在 与 ,使得
记作 。
另有小 (严格上界):对任意 都存在 ;例如 ,但 。
三者的直观区别
| 记号 | 读法 | 类比 | 例子 |
|---|---|---|---|
| 「不超过」 | ,也 | ||
| 「不少于」 | ,也 | ||
| 「恰好是」 | ,唯一确定的那个 | ||
| 「严格小于」 |
别把 当成「精确值」
归并排序说 ,说 在数学上也没错(因为它确实不超过 量级),只是不紧。
工程上我们默认用 表达紧确上界,即想说的是 。
「渐进」两个字的含义
复杂度分析牺牲了三样东西,换来「与机器无关」:
- 忽略常数因子: 和 都写作
- 忽略低阶项: 写作
- 只关心 : 时 可能真的比 快
为什么忽略常数是对的
常数因子受语言、编译器、CPU 影响极大(Python 循环比 C 慢 50 倍),但增长趋势不会变。
当 从 涨到 (1000 倍), 涨约 2000 倍, 涨 1000000 倍。
无论常数多小, 足够大时低阶算法一定输——这就是渐进的威力。
为什么需要它
「跑一遍计时」的五个致命缺陷
import time
def f(n):
s = 0
for i in range(n):
s += i
return s
start = time.perf_counter()
f(1_000_000)
print(f"耗时 {time.perf_counter() - start:.4f} 秒")
这种方法叫 benchmark(基准测试),它有价值,但不能替代复杂度分析:
| 缺陷 | 说明 | 具体后果 |
|---|---|---|
| ① 依赖硬件 | 同一份代码在 M3 笔记本和十年前的服务器上差 10 倍 | 结论无法跨机器复用 |
| ② 依赖语言与实现 | Python 的循环比 C 慢约 50 倍,PyPy 又比 CPython 快 4 倍 | 换个解释器结论就翻转 |
| ③ 只能测已写完的代码 | 设计阶段就要判断方案可行性 | 写完才发现超时,白干 |
| ④ 测不到最坏情况 | 随机数据往往比最坏数据快得多 | 上线后被恶意输入打挂(哈希碰撞攻击就是典型) |
| ⑤ 测不到 很大的情况 | 无法真的跑 | 无法预测规模增长后的表现 |
复杂度分析的核心价值
它是唯一能在「代码还没写」时回答「 能不能在 1 秒内跑完」的工具。
一个经验法则: 在 时是 次操作,任何语言都救不了。
复杂度分析的三个层次
- 粗估:判断 还是 ,决定算法选型
- 精确:算出具体操作次数,指导常数优化
- 实测:用
timeit验证,确认没有隐藏的常数爆炸(如 Python 中list.insert(0, x)是 )
核心内容
一、常见复杂度增长曲线
| 复杂度 | 名称 | 典型算法 | ||||
|---|---|---|---|---|---|---|
| 常数 | 1 | 1 | 1 | 1 | 数组下标访问、哈希查找 | |
| 对数 | 3.3 | 6.6 | 10 | 20 | 二分查找、平衡树查找 | |
| 根号 | 3.2 | 10 | 32 | 1000 | 试除法判素数、分块 | |
| 线性 | 10 | 100 | 一次遍历、计数排序 | |||
| 线性对数 | 33 | 664 | 归并/快速/堆排序 | |||
| 平方 | 100 | 冒泡排序、朴素最短路 | ||||
| 立方 | Floyd、矩阵乘法 | |||||
| 指数 | 1024 | 天文数字 | 不可能 | 枚举子集、朴素背包 | ||
| 阶乘 | 不可能 | 不可能 | 全排列、TSP 暴力 |
时到底要多久
假设一次基本操作耗时 1 纳秒( 秒)——这是现代 CPU 单条简单指令的量级,已经相当乐观:
| 复杂度 | 的操作次数 | 耗时 | 直观感受 |
|---|---|---|---|
| 1 毫秒 | 无感 | ||
| 20 毫秒 | 无感 | ||
| 1 秒 | 勉强 | ||
| 约 16.7 分钟 | 无法接受 | ||
| 约 31.7 年 | 永远等不到 | ||
| 远超宇宙年龄 | 数学上都不可能 |
竞赛与工程的经验阈值
以「1 秒内完成 次基本操作」为基准(C++ 水平,Python 约 ):
| 数据规模 | 可接受的复杂度 |
|---|---|
| | 、 |
| | 、状压 DP |
| | |
| | |
| | 、 |
| | |
| | 、 |
看到题目给的 范围,基本就能反推应该用什么算法——这是最有用的实战技巧。
"""实测:不同复杂度的实际增长(用少量数据外推,验证理论结论)。
运行前请把 n 调小,否则 O(n^2) 那一行会让你等很久。
"""
import time
import math
def timeit(fn, *args, repeat=3):
"""返回最快一次耗时(秒)。取最小值可减少系统调度噪声。"""
best = float("inf")
for _ in range(repeat):
start = time.perf_counter()
fn(*args)
best = min(best, time.perf_counter() - start)
return best
def f_const(n):
return 42
def f_log(n):
c = 0
while n > 1:
n //= 2 # 每次规模减半 -> 循环 log2(n) 次
c += 1
return c
def f_linear(n):
s = 0
for i in range(n):
s += i
return s
def f_nlogn(n):
# 模拟 n log n:外层 n 次,内层 log n 次
s = 0
for i in range(n):
j = n
while j > 1:
j //= 2
s += 1
return s
def f_quadratic(n):
s = 0
for i in range(n):
for j in range(n):
s += 1
return s
if __name__ == "__main__":
for n in (1000, 2000, 4000):
print(
f"n={n:5d} "
f"O(1)={timeit(f_const, n):.2e}s "
f"O(log n)={timeit(f_log, n):.2e}s "
f"O(n)={timeit(f_linear, n):.2e}s "
f"O(n log n)={timeit(f_nlogn, n):.2e}s "
f"O(n^2)={timeit(f_quadratic, n):.2e}s"
)
# 观察规律:n 翻倍时,O(n) 耗时翻倍,O(n log n) 略多于翻倍,
# O(n^2) 耗时变成 4 倍 —— 这就是"增长趋势与机器无关"的直接证据。
二、最好、最坏与平均情况
以快速排序(Quick Sort)的 partition 为例,输入规模 。
| 情况 | 触发条件 | 递推式 | 结果 | 说明 |
|---|---|---|---|---|
| 最好 | 每次划分都均分 | 基准恰好是中位数 | ||
| 平均 | 随机数据 | 随机化后以极高概率均分 | ||
| 最坏 | 每次划分都分成 和 | 已排序数组 + 首元素作基准 |
三种情况的定义与用途
| 情况 | 定义 | 用途 |
|---|---|---|
| 最好情况(Best Case) | 所有输入中代价最小的那个 | 意义最小,仅用于说明「至少不会更差」 |
| 最坏情况(Worst Case) | 所有输入中代价最大的那个 | 最重要:给系统性能上界,是 SLA 与实时系统的依据 |
| 平均情况(Average Case) | 在输入分布上的期望代价 | 反映日常体验,但依赖「输入分布」假设 |
「平均情况」的陷阱
平均情况的结论依赖你假设的输入分布。如果快排假设「所有排列等概率」,那么平均是 ;
但真实数据常常接近有序,固定取首元素作基准就退化成最坏情况。
这就是为什么工程实现要随机化基准或三数取中——它把「输入分布」变成「由算法自己控制的随机性」。
如何选择分析哪种情况
- 写基础库 / 面向不可信输入 → 看最坏情况(要防恶意构造)
- 做数据分析、离线批处理 → 看平均情况
- 需要硬实时保证(如自动驾驶、交易所撮合) → 必须看最坏情况
三、均摊分析(Amortized Analysis)
均摊复杂度研究的不是「单次操作」而是「一串操作序列的总代价平摊到每次」。
均摊 ≠ 平均
平均情况分析要对输入的概率分布做假设;
均摊分析不对输入做任何概率假设,它是对任意操作序列的最坏情况总代价求平均。
换句话说:均摊是确定的保证,不是统计期望。
例子 1:动态数组(list.append)
Python 的 list 底层是动态数组(dynamic array)。容量满时扩容:
Python 的实际策略(CPython list_resize):新容量取
即大约按 增长;其他语言常用 (如 C++ std::vector 的部分实现)或 (如 Java 的 ArrayList)。
聚合法(Aggregate Method) 分析(假设扩容 2 倍,从容量 1 开始):
| 第 次 append | 是否扩容 | 本次拷贝代价 |
|---|---|---|
| 1 | 是(1→2) | 1 |
| 2 | 是(2→4) | 2 |
| 3 | 否 | 1 |
| 4 | 是(4→8) | 4 |
| 5,6,7 | 否 | 1,1,1 |
| 8 | 是(8→16) | 8 |
次 append 的总代价:
结论:list.append 的均摊复杂度是 ,但单次最坏是 。
如果扩容策略是「每次加 1」
那样每次 append 都要拷贝整个数组, 次总代价是 ,均摊 。
成倍扩容是均摊 的关键——这解释了为什么所有标准库都这么写。
"""实现一个动态数组,统计扩容次数与总拷贝元素数,验证均摊 O(1)。"""
class DynamicArray:
def __init__(self, growth=2):
self._data = [None] * 1 # 初始容量 1
self._size = 0
self._cap = 1
self._growth = growth
self.total_copies = 0 # 累计拷贝的元素个数(用于验证均摊)
def append(self, x):
if self._size == self._cap:
self._resize(self._cap * self._growth)
self._data[self._size] = x
self._size += 1
def _resize(self, new_cap):
new_data = [None] * new_cap
for i in range(self._size):
new_data[i] = self._data[i]
self.total_copies += self._size # 记录这次搬了多少个元素
self._data = new_data
self._cap = new_cap
def __len__(self):
return self._size
def verify_amortized(n=1 << 16, growth=2):
a = DynamicArray(growth=growth)
for i in range(n):
a.append(i)
# 均摊 = 总拷贝次数 / n;成倍扩容时应接近常数(< growth/(growth-1))
print(
f"growth={growth} n={n} 总拷贝={a.total_copies} "
f"均摊={a.total_copies / n:.4f} 最终容量={a._cap}"
)
if __name__ == "__main__":
verify_amortized(growth=2) # 实测均摊 ≈ 1.0 个元素 -> O(1)
verify_amortized(growth=3) # 实测均摊 ≈ 0.6 个元素 -> O(1)
# 实测结论:growth=2 时均摊约 1.0 次拷贝/append,growth=3 时约 0.6 次,
# 增长因子越大均摊越低,但都是常数 —— 这就是 O(1) 的含义。
#
# 反面教材:growth=1(每次只把容量加 1 倍,等于不扩)会立刻越界崩溃,
# 因为容量乘以 1 还是原容量。若改成"容量 +1",则每次都全量拷贝,
# 总代价 1+2+...+n = O(n^2),均摊 O(n)。
# 结论:扩容因子必须 > 1,这是均摊 O(1) 的必要条件。
例子 2:并查集的路径压缩
并查集(DSU)只有两个操作:find 与 union。
路径压缩:find(x) 时把路径上所有节点直接挂到根上。单次 find 最坏可以是 (一条长链,第一次查询),但均摊结果非常漂亮:
其中 是反阿克曼函数(Inverse Ackermann Function),它的增长速度慢到荒谬:
| 3 | |
| (宇宙原子数) | 4 |
| 5 |
在一切物理上可写出的 范围内,,所以并查集可以视为 均摊。
这里用势能法(Potential Method)更自然:定义势能 为「所有节点到根的距离之和」,路径压缩会一次性大幅降低 ,从而「预付」了后续操作的代价。这里只做定性说明,严格的势能证明需要引入秩(rank)与 的分级,可参考《算法导论》第 21 章。
"""并查集:路径压缩 + 按秩合并,实测单次操作平均代价趋于常数。"""
import time
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.find_calls = 0
self.total_steps = 0 # 累计 while 循环次数
def find(self, x):
self.find_calls += 1
steps = 0
root = x
while self.parent[root] != root:
root = self.parent[root]
steps += 1
# 路径压缩:把路径上每个点直接指向根
while self.parent[x] != root:
nxt = self.parent[x]
self.parent[x] = root
x = nxt
steps += 1
self.total_steps += steps
return root
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return True
def benchmark(n=200_000):
dsu = DSU(n)
# 先制造一条长链(最坏结构):1 挂到 0,2 挂到 1,...
for i in range(1, n):
dsu.parent[i] = i - 1
start = time.perf_counter()
for i in range(n):
dsu.find(i) # 第一次 find(n-1) 代价 O(n),之后全部被压缩成 O(1)
elapsed = time.perf_counter() - start
print(
f"n={n} find 次数={dsu.find_calls} 平均步数={dsu.total_steps / dsu.find_calls:.3f} "
f"耗时={elapsed:.3f}s"
)
# 平均步数在 1~2 之间 -> 均摊接近 O(1),尽管第一次调用是 O(n)
if __name__ == "__main__":
benchmark()
均摊分析的三种方法
| 方法 | 思路 | 适合场景 |
|---|---|---|
| 聚合法(Aggregate) | 算出 次操作的总代价 ,均摊 = | 动态数组扩容(本文用的方法) |
| 记账法(Accounting) | 给便宜操作多记一点「信用」,供昂贵操作抵扣 | 栈操作、二进制计数器 |
| 势能法(Potential) | 定义势函数 ,均摊代价 = 实际代价 + | 并查集、伸展树(Splay Tree) |
四、递归算法分析
递归算法的代价由递推式(Recurrence)描述。三种求解方法:
方法 1:递归树法(Recursion Tree)
把递归展开成一棵树,每层的代价相加,再乘以层数。
例:归并排序
| 层 | 子问题个数 | 每个规模 | 每层总代价 |
|---|---|---|---|
| 0 | 1 | ||
| 1 | 2 | ||
| 2 | 4 | ||
树高:,共 层。
总代价 。
方法 2:代入法(Substitution / 归纳法)
步骤:① 猜答案;② 用数学归纳法证明;③ 解出常数。
例:证明 满足 。
猜测:(对某个 )。
归纳:假设对所有 成立,则
只要 ,就有 ,于是 。证毕。
代入法的小技巧
减去低阶项时常常会「差一点」,可以适当放大猜测,例如猜 ,
这样归纳时有更大的腾挪空间。这是《算法导论》4.3 节推荐的技巧。
方法 3:主定理(Master Theorem)
对形如
的递推式,令临界指数 ,比较 与 :
| 情况 | 条件 | 结论 | 直觉 |
|---|---|---|---|
| 情况 1 | , | 叶子占主导:递归部分太贵,底层工作量压倒合并 | |
| 情况 2 | , | 每层一样贵: 层各贡献相同 | |
| 情况 3 | 且 , | 根占主导:合并太贵,顶层工作量压倒 |
主定理的三个「不适用」盲区
① 与 只差一个 因子之外的东西,如 ,落在情况 2 与情况 3 之间的缝隙;
② 子问题规模不整齐,如 ;
③ 不是常数,如 。
遇到这些要用递归树或代入法。
主定理例题 1:归并排序
,,,所以 。
,属于情况 2():
主定理例题 2:二分查找
,,,所以 。
,属于情况 2():
主定理例题 3:Strassen 矩阵乘法
,,。
,而 (取 ),属于情况 1:
比朴素矩阵乘法的 快,这是 1969 年 Strassen 的著名突破。
主定理例题 4(情况 3):一个合并极贵的例子
,,,(),
且正则条件满足(,取 ),属于情况 3:
主定理例题 5(易错): 属于哪种情况?
,。,(),
属于情况 3:
直觉:每次递归规模减半,但当前层的代价 支配了一切,几何级数 。
主定理速查实战
| 递推式 | 情况 | 结果 | ||||
|---|---|---|---|---|---|---|
| 2 | 2 | 1 | 2 | |||
| 1 | 2 | 0 | 2 | |||
| 4 | 2 | 2 | 1 | |||
| 7 | 2 | 2.807 | 1 | |||
| 2 | 2 | 1 | 3 | |||
| 8 | 2 | 3 | 1 | |||
| 1 | 3/2 | 0 | 2 | |||
| 3 | 2 | 1.585 | 1 |
"""用递归树/迭代展开法实际求解递推式,并与主定理结论对照。
只适合"子问题规模整齐"的递推式;这里用数值迭代验证增长量级。
"""
import math
def solve_recurrence(a, b, f_desc, n, memo=None):
"""数值求解 T(n) = a*T(n/b) + f(n),用于验证增长量级。
f_desc: 'n' | 'n2' | '1' | 'nlogn'
为避免指数爆炸,只对较小 n 调用;用记忆化减少重复。
"""
if n <= 1:
return 1.0
if memo is None:
memo = {}
if n in memo:
return memo[n]
if f_desc == "n":
f = n
elif f_desc == "n2":
f = n * n
elif f_desc == "1":
f = 1
elif f_desc == "nlogn":
f = n * math.log2(n)
else:
raise ValueError(f_desc)
sub = int(n // b)
res = a * solve_recurrence(a, b, f_desc, sub, memo) + f
memo[n] = res
return res
def master(a, b, f_power, f_log_power=0):
"""按主定理给出结论。f(n) = Theta(n^f_power * log^f_log_power n)。"""
crit = math.log(a, b)
if f_power < crit - 1e-9:
return f"Theta(n^{crit:.3f}) [情况1]"
if abs(f_power - crit) < 1e-9:
return f"Theta(n^{crit:.3f} * log^{f_log_power + 1} n) [情况2]"
return f"Theta(n^{f_power}) [情况3]"
if __name__ == "__main__":
cases = [
(2, 2, "n", 1.0, 0, "归并排序"),
(1, 2, "1", 0.0, 0, "二分查找"),
(4, 2, "n", 1.0, 0, "a=4,b=2"),
(7, 2, "n2", 2.0, 0, "Strassen"),
(2, 2, "n2", 2.0, 0, "合并极贵"),
]
for a, b, fdesc, fp, flp, name in cases:
print(f"{name:12s} 主定理: {master(a, b, fp, flp)}")
# 数值验证:n 翻倍时结果增长的倍数符合预期量级
for n in (1024, 2048, 4096):
print(f" n={n:5d} T(n)={solve_recurrence(a, b, fdesc, n):16.1f}")
五、空间复杂度与递归栈
空间复杂度统计算法运行过程中额外占用的内存,不含输入本身,记作「原地 / 非原地」。
| 来源 | 说明 | 例子 |
|---|---|---|
| 辅助数组 | 显式申请的数组 | 归并排序的合并数组 |
| 递归栈 | 每层递归保存参数、局部变量、返回地址 | 快排最坏 ,平均 |
| 哈希表 | 用于去重或缓存 | 两数之和 |
| 结果存储 | 题目要求输出的一般不计入 | — |
递归栈深度的重要性
递归的空间复杂度 = 最大递归深度,而不是递归调用总次数。
| 算法 | 递归深度 | 栈空间 |
|---|---|---|
| 二分查找 | ||
| 归并排序 | ||
| 快速排序(平均) | ||
| 快速排序(最坏) | ||
| 朴素 DFS(链状图) |
Python 递归的真实限制
CPython 默认递归限制是 1000 层(
sys.getrecursionlimit())。超过就抛
RecursionError: maximum recursion depth exceeded。即使调大
setrecursionlimit,C 栈也可能先溢出导致段错误(Segmentation fault),进程直接崩溃、无法捕获。处理 的深递归(如树的 DFS、图的 DFS)时,正确做法是:
① 改写为显式栈的迭代版本;② 或用
threading.stack_size()起一个大栈线程。
"""空间复杂度与递归深度的实测。"""
import sys
import threading
def depth_recursive(n):
"""最简单的递归:深度 = n,测出实际能跑到多深。"""
if n == 0:
return 0
return 1 + depth_recursive(n - 1)
def measure_python_recursion_limit():
"""二分搜索最大可递归深度,观察 CPython 的实际行为。"""
lo, hi = 1, 200_000
while lo < hi:
mid = (lo + hi + 1) // 2
try:
sys.setrecursionlimit(mid + 200)
depth_recursive(mid)
lo = mid # 没炸,说明还能更深
except RecursionError:
hi = mid - 1
return lo
def run_in_big_stack(n):
"""在大栈线程里跑深递归,绕开 CPython 的默认线程栈限制。"""
result = {}
def worker():
sys.setrecursionlimit(n + 1000)
result["depth"] = depth_recursive(n)
# 默认线程栈往往只有 1~8 MB;32 MB 可以支撑更深的递归
threading.stack_size(64 * 1024 * 1024)
t = threading.Thread(target=worker)
t.start()
t.join()
return result.get("depth")
if __name__ == "__main__":
print("默认递归上限:", sys.getrecursionlimit()) # 通常是 1000
print("不改设置直接跑 5000 深:")
try:
depth_recursive(5000)
except RecursionError as e:
print(" 失败 ->", e) # 印证上面的结论
# 注意:调大限制只解除了 Python 的"计数器",真实的 C 栈上限由解释器的
# 栈空间决定。CPython 3.11+ 对纯 Python 递归做了优化,实测可以跑到
# 数十万层;但在更深或涉及 C 层调用的递归中,仍可能直接段错误。
print("实际可达到的深度约:", measure_python_recursion_limit())
print("大栈线程里跑 100000 深:", run_in_big_stack(100_000))
# 工程结论:不要依赖"调大 setrecursionlimit"来救深递归,
# 稳健做法是改写成显式栈的迭代版本(见 [[数据结构-图]] 的迭代 DFS)。
空间换时间的常见取舍
| 需求 | 选择 |
|---|---|
| 内存紧张(嵌入式) | 原地排序(堆排序 空间) |
| 要求稳定 | 归并排序( 空间) |
| 需要去重 / 计数 | 哈希表( 空间换 查询) |
| 缓存中间结果 | 记忆化搜索 / DP 表( 或 ) |
六、常见算法复杂度速查表
| 算法 | 最好 | 平均 | 最坏 | 空间 | 备注 |
|---|---|---|---|---|---|
| 数组随机访问 | — | ||||
| 链表按下标访问 | 只能在头部 | ||||
| 哈希表查找 | 最坏来自大量冲突 | ||||
| 平衡 BST 查找 | 红黑树、AVL | ||||
| 二分查找 | 必须有序 | ||||
| 冒泡排序 | 稳定 | ||||
| 插入排序 | 稳定,小数组最快 | ||||
| 选择排序 | 交换次数最少 | ||||
| 希尔排序 | 取决于增量 | 不稳定 | |||
| 归并排序 | 稳定 | ||||
| 快速排序 | 不稳定,实际最快 | ||||
| 堆排序 | 不稳定,空间最优 | ||||
| 计数排序 | 要求整数值域小 | ||||
| 基数排序 | 稳定子排序才成立 | ||||
| 桶排序 | 依赖均匀分布 | ||||
| BFS / DFS | 邻接表 | ||||
| Dijkstra(堆优化) | — | 无负权 | |||
| Bellman-Ford | — | 可判负环 | |||
| Floyd-Warshall | — | 多源 | |||
| Kruskal | — | 稀疏图 | |||
| Prim(堆优化) | — | 稠密图 | |||
| 并查集(单次) | 均摊近常数 | ||||
| 0-1 背包(DP) | — | 伪多项式 |
完整排序算法对比见 算法-排序
上图只给了排序的复杂度骨架。稳定性、原地性、递推式与代码实现见专门笔记。
七、P、NP 与 NP 完全问题
问题分类
| 类 | 定义 | 直观 | 例子 |
|---|---|---|---|
| P | 存在多项式时间算法求解的判定问题 | 好解 | 排序、最短路、二分查找、判断图是否连通 |
| NP | 存在多项式时间算法验证一个给定解的问题 | 好验证 | 数独、哈密顿路径、布尔可满足性 |
| NP 难(NP-hard) | 所有 NP 问题都能多项式归约到它(但自己不一定在 NP 中) | 至少一样难 | 旅行商问题的优化版、停机问题 |
| NP 完全(NP-complete) | 既在 NP 中,又是 NP 难 | 难中之难 | SAT、3-SAT、哈密顿回路、旅行商判定版、背包判定版 |
关系:,而 NP 完全问题是 NP 中「最难」的那一批。
为什么说这是开放问题
核心问题: 吗?
- 已知:如果任何一个 NP 完全问题存在多项式算法,那么所有 NP 问题都有多项式算法()
- 已知: 都不被证明——至今没有人能证明 ,也没人能证明
- 这是克雷数学研究所七个千禧年大奖难题之一,悬赏 100 万美元
为什么它这么重要
如果 ,那么:蛋白质折叠、最优物流调度、密码分析(RSA 会被多项式破解)、
自动定理证明、芯片布线优化——所有这些都会变得「可高效求解」。
反过来,如果 (学界普遍相信如此),那么这些问题只能求近似解或启发式解。
现代密码学的安全性就建立在「 且某些问题确实难解」这个(未被证明的)假设之上。
面对 NP 完全问题的工程策略
| 策略 | 说明 | 例子 |
|---|---|---|
| 缩小规模 | 用状态压缩把 压到可行范围() | 状压 DP 解 TSP, |
| 近似算法 | 放弃最优,保证近似比 | TSP 的 Christofides 算法,近似比 1.5 |
| 启发式 / 元启发式 | 无最优保证,实践中很好 | 模拟退火、遗传算法、蚁群算法 |
| 分支限界 | 用上界剪枝,平均情况很快 | 整数规划求解器(Gurobi、CPLEX) |
| 参数化算法 | 复杂度写成 , 为某个小参数 | 顶点覆盖的 算法 |
| 约束求解器 | 交给 SAT / SMT 求解器 | Z3、MiniSat |
"""哈密顿路径(NP 完全)的状压 DP 解法,演示"缩小规模"策略。
状态: dp[mask][v] = 从起点出发、已访问集合为 mask、当前停在 v 是否可行
转移: dp[mask | 1<<u][u] |= dp[mask][v] 若存在边 v->u
复杂度: O(2^n * n^2) —— n=20 时约 4 亿,勉强可跑;n=25 就完全不行了
"""
def hamiltonian_path(n, adj):
"""adj[u] 是 u 的出边集合。返回是否存在哈密顿路径。"""
size = 1 << n
# dp[mask] 用位图表示"以 v 结尾是否可行"
dp = [0] * size
for v in range(n):
dp[1 << v] = 1 << v # 单点路径:以 v 结尾的可行集合是 {v}
for mask in range(size):
if dp[mask] == 0:
continue
ends = dp[mask]
v = 0
while ends:
if ends & 1:
for u in adj[v]:
if not (mask >> u) & 1:
dp[mask | (1 << u)] |= 1 << u
ends >>= 1
v += 1
full = size - 1
return dp[full] != 0
if __name__ == "__main__":
# 5 个点的完全图一定有哈密顿路径
n = 5
adj = [[u for u in range(n) if u != v] for v in range(n)]
print("完全图 K5 有哈密顿路径:", hamiltonian_path(n, adj)) # True
# 去掉一些边后可能没有
n2 = 4
adj2 = [[1], [2], [3], []] # 一条链 0->1->2->3
print("链 0->1->2->3 有哈密顿路径:", hamiltonian_path(n2, adj2)) # True
adj3 = [[1], [0], [3], [2]] # 两个不相连的二元环
print("两个分离二元环:", hamiltonian_path(4, adj3)) # False
八、工程中如何估算性能
四步估算法
第 1 步:确定 的真实量级。 是每天 1000 条还是每秒 100 万条?差 6 个数量级,方案完全不同。
第 2 步:写出复杂度,算出操作次数。
第 3 步:选「每次操作」的单价。 经验值:
| 操作 | 大致耗时 | 说明 |
|---|---|---|
| CPU 一级缓存访问 | 1 ns | 4 个时钟周期 |
| CPU 主存随机访问 | 100 ns | 缓存未命中惩罚 |
| 顺序扫描 1 字节 | ~0.1 ns | 内存带宽约 10 GB/s |
| Python 一次循环迭代 | 30~100 ns | 比 C 慢 30~50 倍 |
| Python 字典查询 | 40~80 ns | C 实现的哈希查找 |
| 磁盘 SSD 随机读 | 100 μs | 比内存慢 1000 倍 |
| 同机房网络往返 | 0.5 ms | — |
| 跨大西洋网络往返 | 150 ms | 光速限制 |
第 4 步:与预算比较。 Web 接口通常要求 P99 < 200 ms;批量任务可以放宽到分钟级。
估算实例:给 1000 万用户发推送
"""估算练习:把"理论复杂度"翻译成"能不能在上线前跑完"。"""
# 场景:10^7 个用户,需要按 (城市, 活跃度) 排序后分批推送
N = 10_000_000
COST_PER_OP = 50e-9 # 保守估计:Python 每次基本操作 50 ns
BUDGET_SECONDS = 300 # 批处理预算:5 分钟
def estimate(name, ops, cost=COST_PER_OP, budget=BUDGET_SECONDS):
seconds = ops * cost
ok = "✅ 通过" if seconds <= budget else "❌ 超预算"
print(
f"{name:28s} 操作数={ops:.3e} 预估耗时={seconds:10.2f}s {ok}"
)
return seconds
if __name__ == "__main__":
import math
print(f"数据规模 n = {N:,},单价 {COST_PER_OP*1e9:.0f} ns/操作,预算 {BUDGET_SECONDS}s\n")
estimate("O(n) 一次遍历", N)
estimate("O(n log n) 排序", N * math.log2(N))
estimate("O(n^1.5) 分块", N ** 1.5)
estimate("O(n^2) 两两比较", N * N)
# 结论:n=10^7 时,O(n) 约 0.5 s、O(n log n) 约 12 s 都可以接受,
# O(n^2) 是 5.8 天,直接淘汰。这就是"先算复杂度再写代码"的价值。
更精确的估算:用
timeit实测单价上面的 50 ns 是保守估计。想知道自己机器上真实单价,用标准库
timeit:```python
import timeit
t = timeit.timeit("for i in range(1000): pass", number=1000)
print(f"每 1000 次循环耗时 {t/1000*1e6:.2f} 微秒")
```
官方文档:https://docs.python.org/3/library/timeit.html
什么时候不该操心复杂度
常数与可读性的权衡
复杂度分析的前提是「 足够大」。如果 永远不超过 50(比如解析一个配置文件的字段),
写 的双重循环远比写一个 的复杂算法更好维护。
优化的第一原则是「先测量,再优化」——不要凭直觉给非热点代码做复杂度优化。
怎么用
快速判断一段代码的复杂度
"""通过几个典型代码片段,练习"数循环"的复杂度判断法。"""
def o1(arr):
return arr[0] if arr else None # 单条语句 -> O(1)
def on(arr):
total = 0
for x in arr: # 循环 n 次
total += x
return total # -> O(n)
def on2(arr):
n = len(arr)
cnt = 0
for i in range(n): # 外层 n 次
for j in range(n): # 内层 n 次
cnt += 1
return cnt # -> O(n^2)
def onlogn(arr):
n = len(arr)
cnt = 0
for i in range(n): # 外层 n 次
j = n
while j > 1: # 内层 log n 次
j //= 2
cnt += 1
return cnt # -> O(n log n)
def on_inner_triangle(arr):
n = len(arr)
cnt = 0
for i in range(n):
for j in range(i + 1, n): # 内层平均 n/2 次
cnt += 1
return cnt # n(n-1)/2 -> 仍是 O(n^2)
def o_log_n_sqrt_n(n):
cnt = 0
i = 1
while i * i <= n: # sqrt(n) 次
j = n
while j > 1:
j //= 2 # log n 次
cnt += 1
i += 1
return cnt # -> O(sqrt(n) log n)
if __name__ == "__main__":
print(o1([1, 2, 3]))
print(on([1, 2, 3]))
print(on2([1, 2, 3]))
print(onlogn([1, 2, 3]))
print(on_inner_triangle([1, 2, 3, 4]))
print(o_log_n_sqrt_n(1000))
数循环的三条规则
| 规则 | 情形 | 结论 |
|---|---|---|
| 加法规则 | 两段顺序代码,复杂度 与 | 总复杂度 |
| 乘法规则 | 循环嵌套 / 递归调用 | 复杂度相乘 |
| 只看最高阶 |
递推式的实用判定流程
遇到 T(n) = a*T(n/b) + f(n)?
├── 子问题规模整齐(都是 n/b)?
│ ├── 是 → 算 c* = log_b(a)
│ │ ├── f(n) 远小于 n^c* → Theta(n^c*) (情况1)
│ │ ├── f(n) 同量级 → Theta(n^c* log n) (情况2)
│ │ └── f(n) 远大于 n^c* → Theta(f(n)) (情况3)
│ └── 否(如 T(n/3)+T(2n/3))→ 用递归树逐层求和
└── 不是标准形式(如 T(sqrt n))→ 换元 或 递归树
注意事项与常见坑
坑 1:把 当精确值比较常数
说「 比 慢一倍」是错的——渐进记号里 。
常数差异要用实测(
timeit)或具体操作计数来比较,不能用大 比。
坑 2:忽略 Python 内建函数的真实复杂度
| 写法 | 真实复杂度 | 常见误解 |
|---|---|---|
|
x in list| | 以为是 ||
list.insert(0, x)| | 以为是 (要整体后移) ||
list.pop(0)| | 应改用collections.deque.popleft()||
list.append(x)| 均摊 | 正确 ||
x in set/x in dict| 平均 ,最坏 | 忽略最坏情况 ||
"a" in "abc"| | 忽略子串匹配代价 ||
sorted(list)| | 正确 ||
lst[a:b]切片 | | 以为是 |
坑 3:在循环里做字符串拼接
```python
# 慢:每轮都新建字符串并复制全部已有内容 -> O(n^2)
s = ""
for x in data:
s += x
# 快:append 均摊 O(1),最后 join 一次 O(n) -> O(n)
parts = []
for x in data:
parts.append(x)
s = "".join(parts)
```
后者是 CPython 官方推荐写法(
''.join()会先算总长度,只分配一次内存)。
坑 4:混淆「均摊」与「最坏」
list.append均摊 ,但单次可能 。对延迟敏感的实时系统(如游戏渲染循环、高频交易),均摊 不等于每一帧都够快——
必须关注单次最坏延迟,必要时用预分配容量来消除扩容抖动。
坑 5:忘了空间复杂度里的递归栈
「我的快排是原地排序,空间 」——错。递归栈平均要 ,最坏 。
真正 空间的排序是堆排序。
坑 6:主定理正则条件被忽略
情况 3 除了要求 ,还要求正则条件 ()。
绝大多数常见的 (多项式、)都满足,但构造性的反例存在。
严格证明时应验证这一步。
坑 7:把「平均情况」当成「所有情况」
哈希表查询平均 ,但如果攻击者能构造大量哈希冲突的键(哈希碰撞攻击),
就能让每次查询退化到 ,把服务打挂。
防御手段:随机化哈希种子(Python 从 3.3 起默认开启
PYTHONHASHSEED随机化)、用平衡树替代链表。
坑 8:误判 是「接近线性」就无所谓
时 ,是 的 20 倍。
对 1 秒预算的服务来说,这 20 倍可能是决定性差异。任何复杂度都要代入具体 算一遍。
坑 9:伪多项式不是多项式
0-1 背包的 看起来像多项式,但 是数值大小而非输入位长。
若 ,输入只需 100 位,而算法要 步。
所以背包问题是 NP 难的——这类复杂度叫伪多项式(Pseudo-polynomial)。
练习题
题 1(基础)判断复杂度
判断下列每段代码的时间复杂度:
# (a)
for i in range(n):
for j in range(n):
for k in range(n):
pass
# (b)
i = n
while i > 1:
i //= 3
# (c)
for i in range(n):
j = 1
while j < n:
j *= 2
# (d)
for i in range(n):
for j in range(i):
pass
<details>
<summary>参考答案</summary>
- (a) :三层各 次的循环相乘
- (b) :每次除以 3,需要 次
- (c) :外层 次,内层 从 1 倍增到 需 次
- (d) :内层次数 ,最高阶是
</details>
题 2(基础)写出递推式
写出「在 个元素中同时找出最大值和最小值,采用分治:把数组分成两半,分别求最值再合并」的递推式并求解。
<details>
<summary>参考答案</summary>
,,,。(),属于情况 1。
结论:分治法求最值仍是线性时间,但比较次数从朴素的 降到约 。
</details>
题 3(中等)用主定理求解下面三个递推式
(1)
(2)
(3)
完整分步解答:
(1)
第 1 步:识别参数。 (子问题个数),(规模缩小倍数),。
第 2 步:计算临界指数。
第 3 步:比较 与 。 ,而 ,所以
第 4 步:判定为情况 1(叶子代价占主导),结论:
第 5 步:直觉验证(递归树)。 第 层有 个子问题,每个规模 ,该层代价 ,随层数递增,所以最后一层最大。
(用到 。)
(2)
第 1 步: ,,。
第 2 步:
第 3 步: ,恰好同量级。
第 4 步:判定为情况 2():
第 5 步:直觉验证。 每层代价都是 ,共 层,总计 。✓
(3)
第 1 步: ,,。
第 2 步:
第 3 步: ,恰好同量级。
第 4 步:判定为情况 2():
第 5 步:直觉验证。 每层代价 ,恒定;层数 ,总计 。✓
</details>
题 4(中等)均摊分析:二进制计数器
一个 位二进制计数器从 0 开始,反复加 1,共加 次。第 位每次翻转的代价是 1。用聚合法证明均摊每次操作代价为 。
完整分步解答:
第 1 步:观察翻转规律。 从 0 数到 :
| 加 1 次数 | 二进制 | 翻转的位 |
|---|---|---|
| 1 | 0001 | 第 0 位 |
| 2 | 0010 | 第 0、1 位 |
| 3 | 0011 | 第 0 位 |
| 4 | 0100 | 第 0、1、2 位 |
| 5 | 0101 | 第 0 位 |
| 6 | 0110 | 第 0、1 位 |
| 7 | 0111 | 第 0 位 |
| 8 | 1000 | 第 0、1、2、3 位 |
第 2 步:统计每一位翻了多少次。
| 位 | 翻转频率 | 次操作的总翻转次数 |
|---|---|---|
| 第 0 位(最低位) | 每次都翻 | |
| 第 1 位 | 每 2 次翻一次 | |
| 第 2 位 | 每 4 次翻一次 | |
| 第 位 | 每 次翻一次 |
第 3 步:求和。
(几何级数 收敛,所以无论 多大,总和都是 。)
第 4 步:均摊。
结论:尽管单次操作最坏要翻转 位,均摊到每次仍是 。✓
</details>
题 5(进阶)为什么快排的最坏情况是 ?
写出快排在「每次划分极不均匀」时的递推式,用代入法求解,并说明随机化为什么能避免它。
<details>
<summary>参考答案</summary>
递推式(每次划分只减少 1 个元素):
展开:
何时发生:数组已经有序(或逆序),且固定取首元素(或末元素)作基准。每次划分只能分出「0 个元素」和「 个元素」。
为什么随机化有效:随机选基准后,任何固定输入都无法保证每次都划分不均——划分结果成为随机变量。可以证明(《算法导论》7.4.2),随机化快排的期望复杂度是 ,且退化到 的概率随 增大指数级下降。
工程实现:除了随机化,还用三数取中(median-of-three)(取首、中、尾三者的中位数作基准)和小区间切换插入排序( 时插入排序更快)。
详见 算法-排序 的快速排序一节。
</details>
题 6(进阶)用估算判断方案可行性
某服务每天要给 条记录做「两两相似度计算」。相似度函数耗时 2 μs。方案 A 是暴力两两比较,方案 B 是用局部敏感哈希(LSH)降到 次函数调用。判断方案 A 是否可行(预算 1 小时)。
<details>
<summary>参考答案</summary>
方案 A:两两比较共
耗时:
远超 1 小时预算,方案 A 不可行。
方案 B:
10 秒,完全可行。(再叠加一次 排序, 次操作,仍可接受。)
结论: 到百万级时, 一律出局,必须降复杂度。
</details>
常见问题 FAQ
Q1:、、 到底哪个"更好"?能给出排序吗?
从小到大的完整顺序是:
判断方法:取极限 。若为 0 则 更小,为 则 更大。
注意 与 、 只是常数倍差异,都写作 。
Q2:为什么算法分析里 的底数不重要?
换底公式:,其中 是常数。
渐进记号忽略常数因子,所以 ,统一写 。
例外:指数中的底数不能忽略——,因为 不是常数。
Q3:主定理能覆盖所有递推式吗?
不能。它只处理 这一种标准形式。三类常见例外:
① 子问题规模不等(,答案是 ,用递归树);
② 规模不是除法而是减法(,直接展开得 );
③ 落在情况之间(如 ,答案是 ,用递归树)。
后者的递归树每层代价 ,求和后得 。
Q4:实际项目里什么时候需要做复杂度分析?
四个时机:① 写代码前选方案(决定用哈希表还是嵌套循环);② Code Review 时识别隐患(发现循环里嵌套了
in list);③ 性能问题定位(用 profiler 找到热点,再判断是复杂度问题还是常数问题);④ 容量规划(预估数据量增长 10 倍后是否还能跑)。日常写 100 行的脚本、处理 1000 条数据时,不需要刻意套用主定理——可读性优先。
Q5:为什么同样的复杂度,Python 比 C 慢几十倍,复杂度分析还有意义?
因为复杂度描述的是增长趋势,趋势与常数无关。 从 涨到 时, 方案无论用 C 还是汇编都会慢 100 倍,而 只慢约 11 倍。
常数决定「起点高低」,复杂度决定「斜率」。数据量足够大时,斜率是决定性的。
但反过来说: 不大时,常数才是关键——这也是为什么小数组用插入排序比快排快。
相关笔记
- 算法-排序:复杂度分析最典型的应用战场,十种排序的对比与递推式
- 数据结构-图:、 等图算法复杂度结论的来源
- 算法-查找与分治:二分查找 与分治递推式的实战
- 算法-动态规划与贪心:伪多项式复杂度与状态空间分析
- 数据结构-树与堆:平衡树 的由来与堆操作复杂度
- 00-索引:全库笔记导航
- 学习路线图:按阶段的学习顺序建议
参考来源
- OI Wiki 复杂度:https://oi-wiki.org/basic/complexity/
- OI Wiki 主定理:https://oi-wiki.org/basic/complexity/#主定理
- MIT OCW 6.006 Introduction to Algorithms(含均摊分析与主定理):https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- Python 官方文档 timeit:https://docs.python.org/3/library/timeit.html
- Python 官方文档 sys.setrecursionlimit:https://docs.python.org/3/library/sys.html#sys.setrecursionlimit
- Python 官方文档 threading.stack_size:https://docs.python.org/3/library/threading.html#threading.stack_size
- CPython 源码 list_resize(动态数组扩容策略):https://github.com/python/cpython/blob/main/Objects/listobject.c
- VisuAlgo 算法可视化:https://visualgo.net/en
- 克雷数学研究所千禧年大奖难题 P vs NP:https://www.claymath.org/millennium-problems/p-vs-np-problem