复杂度分析是对算法资源消耗的数学度量。
为什么重要？
定义：若存在正常数 c 和 n₀，使当 n ≥ n₀ 时 f(n) ≤ c·g(n)，则 f(n) = O(g(n))。
通俗地讲：O 表示上界，刻画的是最坏情况下的渐进增长率。
| 复杂度 | 名称 | 举例 |
|---|---|---|
| O(1) | 常数 | 哈希表查找 |
| O(log n) |
交互式动画演示，可调整参数并单步执行。
全屏打开| 对数 |
| 二分查找 |
| O(n) | 线性 | 数组遍历 |
| O(n log n) | 线性对数 | 归并排序 |
| O(n²) | 平方 | 冒泡排序、暴力枚举 |
| O(n³) | 立方 | Floyd-Warshall |
| O(2ⁿ) | 指数 | 斐波那契递归 |
| O(n!) | 阶乘 | 全排列 |
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) |
|---|---|---|---|---|---|---|
| 10 | 1 | 3 | 10 | 33 | 100 | 1024 |
| 100 | 1 | 7 | 100 | 664 | 10000 | 1.27e30 |
| 1000 | 1 | 10 | 1000 | 9966 | 1e6 | ∞ |
1s 时间能处理的数据规模粗略估计：
- O(n) → 1e7 ~ 1e8
- O(n log n) → 1e6 ~ 1e7
- O(n²) → 1e3 ~ 1e4
- O(2ⁿ) → 20 ~ 25
O(f) + O(g) = O(max(f, g))// O(1) — 常数
int x = arr[0] + arr[1];
// O(log n) — 每次规模减半
while (n > 1) n /= 2;
// O(n) — 单层循环
for (int i = 0; i < n; i++) sum += arr[i];
// O(n log n) — 二分循环 / 排序
for (int i = 0; i < n; i++) binarySearch(arr, target);
// O(n²) — 双层循环
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
sum += arr[i][j];
// O(log² n) — 二分套二分
while (lo < hi) {
int mid = (lo + hi) / 2;
binarySearch(arr, mid);
}对于 T(n) = a·T(n/b) + O(nᵈ)：
| 关系 | 复杂度 |
|---|---|
d > log_b(a) | O(nᵈ) |
d = log_b(a) | O(nᵈ log n) |
d < log_b(a) | O(n^(log_b a)) |
举例：
T(n) = 2T(n/2) + O(n) → O(n log n)T(n) = T(n/2) + O(1) → O(log n)| 复杂度 | 例子 |
|---|---|
| O(1) | 原地交换、双指针 |
| O(log n) | 递归深度为 log n（二分） |
| O(n) | 哈希表、数组、单调栈 |
| O(n²) | 二维 dp、邻接矩阵 |
// 时间 O(2ⁿ)，空间 O(n) — 看起来只是常数
int fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}空间是 O(n)（递归栈深度），不是 O(1)。很多新手栽在这里。
| 名称 | 含义 |
|---|---|
| 最好情况 | 输入最有利时的复杂度 |
| 最坏情况 | 输入最不利时的复杂度（最常用） |
| 平均情况 | 期望复杂度（需要概率分布） |
例：快速排序
均摊复杂度把"偶尔的高代价操作"分摊到"持续的多次调用"上。
// ArrayList 简化版：容量满时扩容 2 倍
public void pushBack(int x) {
if (size == capacity) resize(capacity * 2); // O(n)
arr[size++] = x; // O(1)
}n 次 push：总时间 O(n)，每次均摊 O(1)。
最坏一次扩容 O(n)，倍增扩容约发生 O(log n) 次。
直觉：扩容是"阶段性"成本，分摊到每次 push 上就是 O(1)。
| 方法 | 思路 | 适用 |
|---|---|---|
| 聚合分析 | 总成本 ÷ 调用次数 | 简单均摊 |
| 记账法 | 给每次操作"存钱"，贵操作"取钱" | 操作代价不同 |
| 势能法 | 定义势能函数 Φ，证明总代价 + Φ 增量有界 | 操作代价同 |
public void pushFront(Node x) {
x.next = head;
head = x; // O(1)
}每次都是 O(1)，无均摊问题——但和动态数组的 push_back 不同：链表的 O(1) 没有 cache 友好性。
每个元素最多入栈 / 出栈一次，n 个元素的总体操作 ≤ 2n 次。
均摊 O(1) / 操作，但单次操作最坏 O(n)（例如一次弹掉所有元素）。
这就是为什么"滑动窗口最大值"是 O(n) 而不是 O(n²)。
union(x, y) // O(α(n)) 路径压缩后
find(x) // O(α(n))α 是反 Ackermann 函数，工程上视为常数 ≤ 5。
没有均摊分析就无法解释为什么"看起来递归"的 find 是 O(α)。
| 数据结构 | 查找 | 插入 | 删除 |
|---|---|---|---|
| 数组 | O(n) | O(n) | O(n) |
| 链表 | O(n) | O(1) | O(1) |
| 哈希表 | O(1) | O(1) | O(1) |
| 二分搜索树（平衡） | O(log n) | O(log n) | O(log n) |
| 跳表 | O(log n) | O(log n) | O(log n) |
| B 树 | O(log n) | O(log n) | O(log n) |
| 算法 | 时间 | 空间 |
|---|---|---|
| 二分查找 | O(log n) | O(1) |
| 归并排序 | O(n log n) | O(n) |
| 快速排序 | O(n log n) | O(log n) |
| 堆排序 | O(n log n) | O(1) |
| Dijkstra | O((V+E) log V) | O(V) |
| Floyd | O(V³) | O(V²) |
"你这个算法的复杂度是多少？能优化到多少？"
回答模板：
| 现象 | 优化 |
|---|---|
| O(n²) 暴力 | 用哈希表降到 O(n) |
| O(n) 重复扫描 | 用前缀和 / 双指针 |
| O(n log n) 排序 | 计数排序、基数排序 |
| O(n) 空间 | 滚动数组 / 原地 |
| O(2ⁿ) 暴力 | 记忆化 / DP |
时间换空间，空间换时间。
没有最优的算法，只有最合适的算法。