时间 & 空间复杂度
时间复杂度和空间复杂度是评估算法效率的两个核心指标，帮助我们在不依赖实际运行环境的情况下，量化算法随输入规模增长的资源消耗趋势。
一句话理解
- 时间复杂度：操作次数如何随
n增长？ - 空间复杂度：额外内存消耗如何随
n增长？ - 都用 大 O 符号 表示，关注增长趋势，忽略常数系数。
一、时间复杂度
不计算实际运行时间，而是看操作次数的增长趋势。
常见复杂度（从优到劣）
| 复杂度 | 名称 | 典型算法/场景 |
|---|---|---|
| O(1) | 常数时间 | 数组随机访问、哈希表查找 |
| O(log n) | 对数时间 | 二分查找、平衡二叉树操作 |
| O(n) | 线性时间 | 遍历数组/链表、线性查找 |
| O(n log n) | 线性对数时间 | 归并排序、快速排序（平均） |
| O(n²) | 平方时间 | 冒泡/选择/插入排序、双重循环 |
| O(2ⁿ) | 指数时间 | 穷举所有子集、斐波那契递归 |
| O(n!) | 阶乘时间 | 全排列暴力枚举 |
增长速度对比
n = 100 时，各复杂度操作次数约为：
O(1) → 1
O(log n) → 7
O(n) → 100
O(n log n) → 664
O(n²) → 10,000
O(2ⁿ) → 1,267,650,600,228,229,401,496,703,205,376 ← 完全不可用代码示例
python
# O(1) — 无论 n 多大，操作次数固定
def get_first(arr):
return arr[0]
# O(log n) — 每次排除一半，典型：二分查找
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
# O(n) — 操作次数与 n 成正比
def linear_scan(arr):
for item in arr:
print(item)
# O(n log 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(n²) — 双重循环，典型：冒泡排序
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]如何推导时间复杂度
python
# 技巧：找出执行次数最多的那段代码，看它和 n 的关系
# 单层循环 → O(n)
for i in range(n):
pass
# 双层循环 → O(n²)
for i in range(n):
for j in range(n):
pass
# 每次折半 → O(log n)
i = n
while i > 1:
i = i // 2
# 外层 O(n)，内层 O(log n) → 合计 O(n log n)
for i in range(n):
j = n
while j > 1:
j = j // 2计算规则
- 忽略常数：
O(2n)→O(n)，O(100)→O(1) - 取最高阶：
O(n² + n)→O(n²) - 乘法法则：嵌套循环，复杂度相乘
- 加法法则：顺序执行，取最大值
二、空间复杂度
计算算法运行时占用的"额外"内存，不包括输入数据本身。
常见复杂度
| 复杂度 | 名称 | 典型场景 |
|---|---|---|
| O(1) | 常数空间 | 原地排序、交换两个变量 |
| O(log n) | 对数空间 | 递归二分查找（调用栈深度） |
| O(n) | 线性空间 | 复制数组、哈希表、递归遍历 |
| O(n²) | 平方空间 | 二维矩阵、邻接矩阵存图 |
代码示例
python
# O(1) — 只用了固定数量的变量，与 n 无关
def swap(a, b):
a, b = b, a
return a, b
# O(1) — 原地反转，不申请新数组
def reverse_in_place(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
# O(n) — 申请了一个与 n 等长的新数组
def copy_array(arr):
return [x for x in arr]
# O(n) — 递归调用栈深度为 n
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1) # 调用栈会积累 n 层
# O(n²) — 生成 n×n 的二维矩阵
def create_matrix(n):
return [[0] * n for _ in range(n)]递归的空间复杂度
递归函数每次调用都会在调用栈上压入一帧，因此：
- 递归深度为
n→ 空间复杂度O(n) - 递归深度为
log n（如二分递归）→ 空间复杂度O(log n) - 尾递归优化后栈帧复用 → 理论上可降到
O(1)（Python 不支持，Java/C 支持）
三、时间 vs 空间的权衡
两者往往是矛盾的 — 想跑得更快，通常需要多占内存；想省内存，通常需要多花时间。
| 策略 | 含义 | 典型例子 |
|---|---|---|
| 空间换时间 | 用更多内存换取更快的速度 | 哈希表、缓存（Memoization）、预计算查表 |
| 时间换空间 | 减少内存使用，接受更慢的速度 | 流式处理大文件、迭代替代递归 |
典型案例
案例一：哈希表（空间换时间）
python
# 暴力查找两数之和 — O(n²) 时间，O(1) 空间
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
# 哈希表优化 — O(n) 时间，O(n) 空间（用空间换了时间）
def two_sum_hash(nums, target):
seen = {} # 额外 O(n) 空间
for i, num in enumerate(nums):
complement = target - num
if complement in seen: # O(1) 查找
return [seen[complement], i]
seen[num] = i案例二：斐波那契（Memoization 缓存）
python
# 纯递归 — O(2ⁿ) 时间，大量重复计算
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
# 记忆化递归 — O(n) 时间，O(n) 空间（缓存中间结果）
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
# 迭代 — O(n) 时间，O(1) 空间（时间换空间的反例：这里两者都优）
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a工程实践中的取舍原则
- 优先优化时间复杂度：内存便宜，CPU 时间是用户体验的直接感知
- 内存受限时关注空间：嵌入式、移动端、大数据场景内存是瓶颈
- 缓存是最常见的空间换时间：Redis、本地缓存、CDN 本质都是这个思路
- 流式处理是最常见的时间换空间：处理 TB 级文件时不可能全部加载进内存
四、常见算法复杂度速查
| 算法 | 时间（最好） | 时间（平均） | 时间（最坏） | 空间 |
|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) |
| 二分查找 | O(1) | O(log n) | O(log n) | O(1) |
| 哈希表查找 | O(1) | O(1) | O(n)* | O(n) |
| DFS / BFS | — | O(V+E) | O(V+E) | O(V) |
* 哈希表最坏情况为所有 key 哈希碰撞退化为链表，实际极少发生。