1. 为什么需要复杂度分析
算法复杂度分析是衡量算法效率的标准方法，它不依赖具体的机器环境，而是从问题规模增长的角度评估性能。
同一套代码在 i3 和 i9 上运行时间不同，但它们的增长趋势是一致的。
2. 时间复杂度
2.1 大 O 记号（Big-O Notation）
Big-O 描述的是算法执行时间随输入规模 n 增长的上界（最坏情况）。
常见复杂度等级（从优到劣）：
| 复杂度 | 名称 | 示例 |
|---|---|---|
| O(1) | 常数 | 数组随机访问 |
| O(log n) | 对数 | 二分查找 |
| O(n) | 线性 | 遍历数组 |
| O(n log n) | 线性对数 | 快速排序、归并排序 |
| O(n²) | 平方 | 双重循环（冒泡排序） |
| O(n³) | 立方 | 三重循环（矩阵乘法基础） |
| O(2ⁿ) | 指数 | 递归求解子集 |
| O(n!) | 阶乘 | 全排列 |
2.2 如何计算时间复杂度
原则：关注最高阶项，忽略常数系数和低阶项。
# 示例 1：O(n)
def sum_array(arr):
total = 0
for x in arr: # n 次
total += x
return total
# 示例 2：O(n²)
def find_pairs(arr):
for i in range(len(arr)):
for j in range(len(arr)): # n * n
print(arr[i], arr[j])
# 示例 3：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
# 示例 4：O(n log n)
def efficient_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2 # O(1)
left = efficient_sort(arr[:mid]) # T(n/2)
right = efficient_sort(arr[mid:]) # T(n/2)
return merge(left, right) # O(n)
# 递推：T(n) = 2T(n/2) + O(n) → O(n log n)
2.3 最好、最坏、平均情况
| 情况 | 定义 | 示例 |
|---|---|---|
| 最好 | 最理想输入 | 冒泡排序已有序数组：O(n) |
| 最坏 | 最不利输入 | 快速排序每次选到最大/最小值：O(n²) |
| 平均 | 随机输入期望 | 快速排序平均：O(n log n) |
3. 空间复杂度
空间复杂度衡量算法执行过程中额外占用的存储空间随 n 的增长趋势。
# O(1) 额外空间
def reverse_inplace(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
# O(n) 额外空间
def copy_double(arr):
result = [] # 额外创建 n 个元素
for x in arr:
result.append(x * 2)
return result
# O(n) 递归栈空间
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1) # 深度为 n 的调用栈
# O(log n) 递归栈空间（二分递归）
def fib_log_space(n):
if n <= 1:
return n
return fib_log_space(n - 1) + fib_log_space(n - 2) # 实际上为 O(n)，这里需要更准确说明
4. 复杂度对比图
n=10 时的对比：
O(1) ████ 1
O(log n) ██████ 3.3
O(n) ████████████████████ 10
O(n log n) █████████████████████████████████████ 33
O(n²) ████████████████████████████████████████████████████████████████████████████████████████████ 100
O(2ⁿ) ... (极长，1024)
5. 主定理（Master Theorem）
用于快速求解分治算法的时间复杂度：
T(n) = aT(n/b) + f(n)
| 条件 | 结果 |
|---|---|
| f(n) = O(nᶜ), c < logᵦa | T(n) = Θ(n^(logᵦa)) |
| f(n) = Θ(n^(logᵦa)) | T(n) = Θ(n^(logᵦa) log n) |
| f(n) = Ω(nᶜ), c > logᵦa | T(n) = Θ(f(n)) |
示例： 归并排序 T(n) = 2T(n/2) + O(n)
- a = 2, b = 2, log₂2 = 1
- f(n) = O(n¹)，符合 case 2
- 因此 T(n) = Θ(n log n)
6. 复杂度分析实战
6.1 面试高频题
# 求以下代码时间复杂度
def foo(n):
i = 1
while i < n:
i = i * 2
print(i)
# 答案：O(log n)，因为 i 呈指数增长
# 求以下代码时间复杂度
def bar(n):
for i in range(n):
j = 1
while j < n:
j = j * 2
print(i, j)
# 答案：O(n log n)，外层 n 次，内层 log n 次
6.2 空间换时间 vs 时间换空间
# 空间换时间：两数之和
# 暴力 O(n²) → 哈希表 O(n)
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
7. 总结
| 概念 | 要点 |
|---|---|
| Big-O | 渐进上界，描述最坏情况 |
| Big-Ω | 渐进下界，描述最好情况 |
| Big-Θ | 紧致界，当上界=下界时使用 |
| 常见陷阱 | 递归注意栈空间、嵌套循环不一定 O(n²) |
核心原则：复杂度分析是算法选型的第一依据。在工程实践中，O(n²) 在 n > 10⁴ 时通常不可接受，O(n log n) 是大多场景的性能锚点。
参考文章
- 下一篇：数组、链表与线性表
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。