复杂度分析

本章目标：掌握大 O 表示法，能在 30 秒内估算代码的时间与空间复杂度。

你将学到

• 大 O 表示法的定义与含义
• 常见复杂度等级的对比
• 空间复杂度的计算
• 主定理（Master Theorem）及应用
• 均摊分析的概念
• 1 秒内能处理多大规模的数据

1. 概念

大 O 表示法描述的是算法运行时间（或空间）随输入规模 n 增长的上界。它忽略常数因子和低阶项，只关注增长趋势。例如 3n² + 5n + 100 的大 O 为 O(n²)。

理解复杂度的核心在于：当 n 趋于无穷大时，哪一项主导了增长。

常见复杂度对比

复杂度	名称	n=10	n=100	n=1000	n=10⁶	典型算法
O(1)	常数	1	1	1	1	哈希表查找
O(log n)	对数	3	7	10	20	二分查找
O(n)	线性	10	100	10³	10⁶	数组遍历
O(n log n)	线性对数	33	664	10⁴	2×10⁷	归并排序
O(n²)	平方	100	10⁴	10⁶	10¹²	冒泡排序
O(2ⁿ)	指数	1024	极大	天文数字	天文数字	暴力求子集
O(n!)	阶乘	3628800	天文数字	—	—	全排列

1 秒能算多大 n

竞赛和面试中，通常假设每秒执行约 10⁸ 次基本运算：

• O(n)：n 可达 10⁸
• O(n log n)：n 可达 10⁶
• O(n²)：n 可达 10⁴
• O(n³)：n 可达 500
• O(2ⁿ)：n 不超过 25
• O(n!)：n 不超过 12

看到题目数据范围，就应该知道需要什么复杂度的算法。

2. 主定理（Master Theorem）

用于分析分治递归 T(n) = aT(n/b) + f(n) 的复杂度：

比较 f(n) 与 n^(log_b a)：

Case 1: f(n) = O(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))

经典例子：

• 归并排序：T(n) = 2T(n/2) + O(n) → a=2, b=2, f(n)=n → Case 2 → O(n log n)
• 二分查找：T(n) = T(n/2) + O(1) → a=1, b=2, f(n)=1 → Case 2 → O(log n)
• 快速幂：T(n) = T(n/2) + O(1) → O(log n)

3. 均摊分析

某些操作单次最坏复杂度很高，但连续执行 n 次的总复杂度很低。

经典例子：动态数组扩容（如 Swift 的 Array、C++ 的 vector）

// 每次 append 平均 O(1)，但偶尔触发扩容 O(n)
var arr: [Int] = []
for i in 0..<n {
    arr.append(i)  // 均摊 O(1)
}
// 总时间 O(n)，均摊每次 O(1)

扩容策略通常是容量翻倍，n 次 append 的总拷贝次数为 1+2+4+...+n ≈ 2n，所以均摊 O(1)。

4. 空间复杂度

空间复杂度计算原则：

• 递归调用栈深度计入空间复杂度
• 输入数组本身不计入额外空间
• DP 的滚动数组优化可把 O(n²) 降到 O(n)

# 空间 O(n) — 需要额外数组
def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

# 空间 O(1) — 原地操作
def reverse(arr):
    i, j = 0, len(arr) - 1
    while i < j:
        arr[i], arr[j] = arr[j], arr[i]
        i += 1; j -= 1

5. 易错点

• ⚠️ 字符串拼接在循环中可能隐藏 O(n²) 复杂度
• ⚠️ 递归不记忆化可能导致 O(2ⁿ) 指数爆炸（如朴素递归斐波那契）
• ⚠️ 排序后再二分，总体是 O(n log n) 而非 O(log n)
• ⚠️ 哈希表最坏情况是 O(n)，但平均 O(1)，面试中一般说平均复杂度

推荐刷题清单

题号	题名	难度	关键
169	多数元素	Easy	均摊分析
912	排序数组	Medium	复杂度对比

延伸阅读

• LeetCode 官方
• 代码随想录
• 《算法导论》(CLRS) 第 1-3 章