复杂度分析入门
面试必问：你的解法时间复杂度是多少？
什么是复杂度？
复杂度描述了算法执行时间或占用空间如何随输入规模增长而变化。
时间复杂度
常见时间复杂度（从快到慢）
| 符号 | 名称 | 例子 |
|---|---|---|
| O(1) | 常数 | 数组随机访问 |
| O(log n) | 对数 | 二分查找 |
| O(n) | 线性 | 遍历数组 |
| O(n log n) | 线性对数 | 快速排序、归并排序 |
| O(n²) | 平方 | 双重循环、冒泡排序 |
| O(2ⁿ) | 指数 | 暴力递归（斐波那契） |
| O(n!) | 阶乘 | 全排列 |
如何分析？
规则 1：只保留最高阶
# O(n) + O(n²) = O(n²)
for i in range(n): # O(n)
pass
for i in range(n): # O(n²)
for j in range(n):
pass
规则 2：忽略常数系数
# O(3n) = O(n)
for i in range(n): pass
for i in range(n): pass
for i in range(n): pass
规则 3：嵌套循环相乘
# O(n * m)
for i in range(n):
for j in range(m):
pass
空间复杂度
描述算法额外使用的内存。
| 符号 | 例子 |
|---|---|
| O(1) | 只用几个变量 |
| O(n) | 创建与输入等长的数组 |
| O(n²) | 创建 n×n 的矩阵 |
常见算法复杂度速查
| 算法 | 时间 | 空间 |
|---|---|---|
| 数组遍历 | O(n) | O(1) |
| 二分查找 | O(log n) | O(1) |
| 快速排序 | O(n log n) | O(log n) |
| 归并排序 | O(n log n) | O(n) |
| BFS/DFS | O(V + E) | O(V) |