元数据卡
- 前置知识：大 O 记号的基本概念（上一页）
- 预计时间：10 分钟
- 完成标志：能对常见代码模式分析出复杂度
如何分析一段代码的复杂度
分析复杂度有一套固定的方法。不是猜——是推。
单循环：O(n)
python
def sum_array(arr):
total = 0
for x in arr: # 执行 n 次
total += x # 每次执行 O(1)
return total # O(1)循环执行 n 次，每次是常数操作 → O(n)
嵌套循环：O(n²)
python
def print_pairs(arr):
for i in range(len(arr)): # n 次
for j in range(len(arr)): # 每次内层 n 次
print(arr[i], arr[j]) # O(1)外层 n 次，内层每次 n 次 → O(n × n) = O(n²)
对数时间：O(log n)
python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1每次循环把搜索范围减半。2ᵏ = n 次后找到 → k = log₂ n → O(log n)
递归的复杂度
递归函数的复杂度分析需要额外小心。
python
def factorial(n): # T(n) = T(n-1) + O(1)
if n <= 1:
return 1
return n * factorial(n - 1)每次递归调用自己一次，参数减 1，递归深度 n → O(n)
python
def fibonacci(n): # T(n) = T(n-1) + T(n-2) + O(1)
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)每次调用分裂成两个，形成一颗二叉树，节点数约 2ⁿ → O(2ⁿ)
这就是为什么 naive Fibonacci 在 n=50 时就跑不动了——不是电脑慢，是指数增长的本质。
空间复杂度也同样重要。递归函数的每次调用都会在调用栈上占据一层。
factorial(1000)需要 O(n) 的栈空间——1000 层。如果递归太深会栈溢出。
空间复杂度速查
| 模式 | 空间复杂度 | 说明 |
|---|---|---|
| 只用了几个变量 | O(1) | 不随输入增长 |
| 创建了一个和输入等大的数组 | O(n) | 额外空间随输入线性增长 |
| 递归深度 n | O(n) | 调用栈消耗 |
| 创建了 n x n 的矩阵 | O(n²) | 空间平方增长 |
实战：分析一段真实代码
python
def find_most_common(arr):
counts = {}
for x in arr:
if x in counts:
counts[x] += 1
else:
counts[x] = 1
max_count = 0
most_common = None
for key, val in counts.items():
if val > max_count:
max_count = val
most_common = key
return most_common分析：
- 第一个循环遍历 n 个元素 → O(n)
- 第二个循环遍历 m 个唯一元素（m ≤ n）→ O(m) ≤ O(n)
- 总时间：O(n) + O(m) → O(n)
- 空间：哈希表存了最多 n 个元素 → O(n)
旅人笔记
分析复杂度有固定的套路：单循环 O(n)，嵌套循环 O(n²)，每次减半 O(log n)，递归分裂 O(2ⁿ)。空间复杂度别忘了递归调用的栈消耗。
→ 下一步：数组与链表
复杂度分析是评判算法的尺子。有了尺子，我们开始看真正的数据结构。