算法复杂度分析
一份日报需要统计每位客户的订单总额。100 位客户和 1,000 笔订单时,逐个客户扫描全部订单还能接受;增长到 10 万位客户和 100 万笔订单后,同样的写法要做约 1,000 亿次编号比较。复杂度分析用输入规模描述工作量怎样增长,帮助判断问题出在算法结构,还是常数开销和运行环境。
先定义规模,再数主要操作
用 n 表示客户数、m 表示订单数。两者独立增长,不能在没有依据时都写成 n。下面的直接实现为每位客户遍历全部订单,比较次数恰好是 n × m。
python
def totals_by_scan(customer_ids, orders):
totals = {}
for customer_id in customer_ids:
total = 0
for order in orders:
if order["customer_id"] == customer_id:
total += order["amount_cents"]
totals[customer_id] = total
return totals金额使用整数分,避免把浮点精度问题混进算法比较。假设单次编号比较、整数加法及字典访问的成本可按固定大小数据近似处理,这段程序的时间是 Θ(nm)。输出字典占 O(n);不算输出时,循环只维护少量变量,辅助空间为 O(1)。
另一种写法先按客户编号汇总全部订单,再查出目标客户的结果。它改变的是遍历结构:订单只处理一遍,客户也只处理一遍。
python
def totals_by_index(customer_ids, orders):
amounts = {}
for order in orders:
customer_id = order["customer_id"]
amounts[customer_id] = amounts.get(customer_id, 0) + order["amount_cents"]
return {customer_id: amounts.get(customer_id, 0) for customer_id in customer_ids}设订单里有 k 个不同客户编号。在哈希查找和插入平均为常数时间的假设下,第二种实现的期望时间为 Θ(n + m),汇总索引额外占 O(k) 空间,输出仍占 O(n)。哈希表并不保证任意输入的单次最坏时间都是 O(1);键的散列、相等比较成本和冲突都可能改变实际表现。
这里以额外空间换掉了重复扫描。若订单文件不能一次装入内存,可以逐行汇总,避免保存完整订单列表;如果不同客户也多到无法放入内存,就需要分批、外部排序或交给数据库聚合。不能只看到时间更小,就忽略内存上限。
渐近记号与输入情况是两个维度
O 表示渐近上界,Ω 表示渐近下界,Θ 表示紧确界。它们都描述某个成本函数随规模增长的界限,不分别对应最坏、最好和平均情况。
| 记号 | 含义 | 例子 |
|---|---|---|
f(n) = O(g(n)) | 规模足够大时,f 不超过 g 的某个正常数倍 | 3n + 2 = O(n),也属于 O(n²),后者更宽松 |
f(n) = Ω(g(n)) | 规模足够大时,f 不低于 g 的某个正常数倍 | 3n + 2 = Ω(n) |
f(n) = Θ(g(n)) | 同时有同阶上界和下界 | 3n + 2 = Θ(n) |
f(n) = o(g(n)) | f/g 趋近于 0,增长严格更慢 | n = o(n log n) |
f(n) = ω(g(n)) | f/g 趋向无穷,增长严格更快 | n log n = ω(n) |
再看顺序查找。目标就在第一个元素时只比较一次,最好情况是 Θ(1);目标不存在或位于最后时,要检查整个序列,最坏情况是 Θ(n)。假设目标必然存在且等概率位于任一位置,平均比较次数是 (n + 1) / 2,平均情况也是 Θ(n)。平均情况必须说明输入分布,不能凭“通常挺快”推导。
因此,“最坏时间的上界是 O(n)”同时说明了输入情况和界限;只写“大 O 就是最坏情况”会把这两个维度混在一起。
常见结构怎样推导
连续执行两段独立循环,工作量相加,如 3n + 2m 归为 Θ(n + m)。内层循环每次都完整执行时,工作量相乘;但看到两层循环不能直接断定 O(n²)。双指针若在整个过程中各自只向前移动最多 n 次,总工作量仍可为 O(n)。
每次将搜索范围减半,约 log₂ n 次后范围降到 1,因此已排序数组上的二分查找是 O(log n)。如果先把无序数据排序再查一次,还要计入排序成本;不能只计算最后那一步查找。具体边界更新见 搜索算法。
归并排序把长度 n 的输入拆成两半,递归求解后用线性时间合并,递推关系为 T(n) = 2T(n/2) + Θ(n)。每层合计处理约 n 个元素,共约 log₂ n 层,所以时间为 Θ(n log n)。这来自该算法的拆分与合并方式,不表示所有分治算法都有相同复杂度,见 分治算法。
| 增长阶 | 典型结构 | 输入翻倍后的主要工作量变化 |
|---|---|---|
Θ(1) | 固定次数访问 | 基本不变 |
Θ(log n) | 每轮减半 | 增加一个固定量,底为 2 时约多一轮 |
Θ(n) | 单次完整扫描 | 约 2 倍 |
Θ(n log n) | 归并排序 | 略多于 2 倍 |
Θ(n²) | 两个同规模集合的全量配对 | 约 4 倍 |
Θ(2ⁿ) | 枚举 n 个元素的所有子集 | 翻倍为 2^(2n),原工作量的平方 |
表格只描述主要增长项。输入很小时,初始化、函数调用、内存分配等常数可能决定速度;存在磁盘、网络或 GPU 操作时,还应按相应资源建立成本模型。
递归空间和摊还成本
递归除了结果本身,还要计算调用栈。一个深度为 n、每层保留固定大小局部状态的递归,栈空间是 O(n);不是代码里没有显式创建数组就算 O(1)。切片和复制也会分配内存,要区分同时存活的空间峰值与整个执行过程累计分配的内存量。
动态数组扩容则说明了“单次最坏”和“连续操作平均成本”的区别。在容量从 1、2、4、8 逐次翻倍的模型里,某次追加可能复制已有的 n 个元素,单次最坏为 O(n);但连续追加 n 次时,复制量是 1 + 2 + 4 + … < 2n,加上 n 次写入,总成本仍为 O(n),每次摊还 O(1)。
摊还分析不依赖输入出现的概率,与平均情况分析不同。这里使用的是简化的倍增模型,不能据此断言某门语言的动态数组总是按二倍扩容。
用结果和测量验证判断
先核对两种实现输出一致,再测量规模增长。下面的样例可以和前面的两个函数放在同一个文件中运行,不依赖第三方包:
python
from timeit import repeat
for n in (100, 200, 400):
customer_ids = list(range(n))
orders = [
{"customer_id": i % n, "amount_cents": 100}
for i in range(10 * n)
]
expected = {customer_id: 1000 for customer_id in customer_ids}
assert totals_by_scan(customer_ids, orders) == expected
assert totals_by_index(customer_ids, orders) == expected
for fn in (totals_by_scan, totals_by_index):
samples = repeat(lambda: fn(customer_ids, orders), number=3, repeat=5)
print(n, fn.__name__, min(samples) / 3)
assert totals_by_scan([1], []) == totals_by_index([1], []) == {1: 0}
assert totals_by_scan([], []) == totals_by_index([], []) == {}这里让 m = 10n,所以规模翻倍时,扫描法的编号比较次数从 10n² 变为 40n²,索引法处理的记录数从约 11n 变为约 22n。实测时间未必精确呈四倍或两倍,但应结合多组规模观察趋势。输入构造放在计时外,重复运行取较小值用于减少调度噪声;它不能代替生产请求的 P95/P99 延迟统计。
该实验使用很小的整数和内存中的规则数据,验证的是遍历结构的差异。真实日报还应测量文件读取、不同客户数带来的内存峰值、异常记录比例和输出写入。算法增长阶、资源上限和业务结果都符合要求后,优化才算完成闭环。
