复杂度与数据规模复杂度与数据规模
从输入规模反推算法上限，掌握均摊、递归与空间复杂度。从输入规模反推算法上限，掌握均摊、递归与空间复杂度。
专题导读
复杂度不是为了给代码贴标签，而是用输入规模预测程序是否能在时间与内存限制内完成。面试中应先根据 n 的范围确定复杂度上限，再选择算法；写完代码后，还要能解释最坏情况、额外空间和隐藏常数。复杂度不是为了给代码贴标签，而是用输入规模预测程序是否能在时间与内存限制内完成。实践中应先根据 n 的范围确定复杂度上限，再选择算法；写完代码后，还要能解释最坏情况、额外空间和隐藏常数。
学完本章，你应该能够
- 根据数据规模快速判断可接受的时间复杂度根据数据规模快速判断可接受的时间复杂度
- 正确分析顺序、嵌套、折半和递归代码正确分析顺序、嵌套、折半和递归代码
- 区分最坏、平均、均摊复杂度以及额外空间区分最坏、平均、均摊复杂度以及额外空间
- 避免只看循环层数、忽略输入分布和语言开销避免只看循环层数、忽略输入分布和语言开销
从数据规模倒推算法从数据规模倒推算法
先看约束，再想算法。下面是竞赛与面试环境中的经验值，不是严格边界，但足以用于第一轮方案筛选。先看约束，再想算法。下面是编码评测环境中的经验值，不是严格边界，但足以用于第一轮方案筛选。
通常可以把 1 秒内可执行的简单操作粗略估算为 10⁷ 到 10⁸ 次。Java 代码还会受到 JIT 预热、自动装箱、对象分配、GC 与集合常数开销影响，因此复杂逻辑应保守估计。通常可以把 1 秒内可执行的简单操作粗略估算为 10⁷ 到 10⁸ 次。Java 代码还会受到 JIT 预热、自动装箱、对象分配、GC 与集合常数开销影响，因此复杂逻辑应保守估计。
当 n 达到 10⁵ 时，O(n²) 几乎一定不可行；当 n 只有 20 左右时，2ⁿ 的状态枚举反而可能是正确方向。当 n 达到 10⁵ 时，O(n²) 几乎一定不可行；当 n 只有 20 左右时，2ⁿ 的状态枚举反而可能是正确方向。
输入规模与常见复杂度上限输入规模与常见复杂度上限
| 输入规模 n输入规模 n | 通常可接受通常可接受 | 常见方法常见方法 |
|---|---|---|
| n ≤ 10n ≤ 10 | O(n!)O(n!) | 全排列、暴力搜索全排列、暴力搜索 |
| n ≤ 20n ≤ 20 | O(2ⁿ · n)O(2ⁿ · n) | 状态压缩、子集枚举状态压缩、子集枚举 |
| n ≤ 10³n ≤ 10³ | O(n²)O(n²) | 二维 DP、两两比较二维 DP、两两比较 |
| n ≤ 10⁵n ≤ 10⁵ | O(n log n)O(n log n) | 排序、堆、分治排序、堆、分治 |
| n ≤ 10⁶n ≤ 10⁶ | O(n)O(n) | 扫描、哈希、双指针扫描、哈希、双指针 |
| n ≥ 10⁷n ≥ 10⁷ | O(log n) / O(1)O(log n) / O(1) | 数学推导、二分、预处理数学推导、二分、预处理 |
判断顺序判断顺序
数据规模 → 时间上限 → 候选复杂度 → 数据特征 → 具体算法。不要先套模板，再回头验证是否超时。数据规模 → 时间上限 → 候选复杂度 → 数据特征 → 具体算法。不要先套模板，再回头验证是否超时。
渐进复杂度的计算规则渐进复杂度的计算规则
Big-O 关注 n 增大时的增长趋势，因此忽略常数项和低阶项，但不能忽略不同变量。Big-O 关注 n 增大时的增长趋势，因此忽略常数项和低阶项，但不能忽略不同变量。
顺序执行取最大项顺序执行取最大项
O(n) + O(n log n) + O(1) 最终记为 O(n log n)，因为高阶项主导增长。O(n) + O(n log n) + O(1) 最终记为 O(n log n)，因为高阶项主导增长。
嵌套循环通常相乘嵌套循环通常相乘
两层都遍历 n 次是 O(n²)；若内层只遍历到 i，总次数为 1+2+…+n，仍是 O(n²)。两层都遍历 n 次是 O(n²)；若内层只遍历到 i，总次数为 1+2+…+n，仍是 O(n²)。
指针单调移动看总次数指针单调移动看总次数
双指针即使写成 while 套 while，只要左右指针都不回退，总移动次数通常是 O(n)，不是 O(n²)。双指针即使写成 while 套 while，只要左右指针都不回退，总移动次数通常是 O(n)，不是 O(n²)。
规模每次减半是对数规模每次减半是对数
二分查找、堆高度以及不断执行 n = n / 2 的循环，迭代次数为 O(log n)。二分查找、堆高度以及不断执行 n = n / 2 的循环，迭代次数为 O(log n)。
多个输入变量分别保留多个输入变量分别保留
遍历两个独立数组应写 O(n + m)，不能在没有关系时简化成 O(n)。遍历两个独立数组应写 O(n + m)，不能在没有关系时简化成 O(n)。
| 复杂度复杂度 | 增长特征增长特征 | 典型场景典型场景 |
|---|---|---|
| O(1)O(1) | 与输入规模无关与输入规模无关 | 数组下标访问、哈希平均查询数组下标访问、哈希平均查询 |
| O(log n)O(log n) | 每轮排除固定比例每轮排除固定比例 | 二分查找、平衡树操作二分查找、平衡树操作 |
| O(n)O(n) | 完整扫描一次完整扫描一次 | 计数、双指针、哈希建表计数、双指针、哈希建表 |
| O(n log n)O(n log n) | 线性层工作 × 对数层数线性层工作 × 对数层数 | 比较排序、归并分治比较排序、归并分治 |
| O(n²)O(n²) | 所有二元组合所有二元组合 | 简单二维 DP、两两比较简单二维 DP、两两比较 |
| O(2ⁿ)O(2ⁿ) | 枚举所有子集枚举所有子集 | 回溯、状态压缩回溯、状态压缩 |
均摊分析与隐藏成本均摊分析与隐藏成本
单次操作很贵，不代表一系列操作都很贵。均摊复杂度把偶发的扩容或清理成本分摊到整个操作序列。单次操作很贵，不代表一系列操作都很贵。均摊复杂度把偶发的扩容或清理成本分摊到整个操作序列。
ArrayList 容量不足时会申请更大数组并复制已有元素，某一次 add 是 O(n)，但容量按比例增长时，连续 n 次 add 的总复制量仍为 O(n)，因此平均每次是 O(1)。ArrayList 容量不足时会申请更大数组并复制已有元素，某一次 add 是 O(n)，但容量按比例增长时，连续 n 次 add 的总复制量仍为 O(n)，因此平均每次是 O(1)。
哈希表查询通常写作平均 O(1)，但极端冲突下可能退化。面试表达时应说明依赖良好的哈希函数、合理负载因子和扩容策略。哈希表查询通常写作平均 O(1)，但极端冲突下可能退化。实践表达时应说明依赖良好的哈希函数、合理负载因子和扩容策略。
动态数组扩容动态数组扩容
单次最坏 O(n)，连续追加的均摊复杂度 O(1)。单次最坏 O(n)，连续追加的均摊复杂度 O(1)。
单调栈单调栈
元素可能在 while 中连续出栈，但每个元素最多入栈、出栈各一次，总复杂度 O(n)。元素可能在 while 中连续出栈，但每个元素最多入栈、出栈各一次，总复杂度 O(n)。
路径压缩并查集路径压缩并查集
单次操作不是严格 O(1)，多次操作的均摊复杂度接近常数。单次操作不是严格 O(1)，多次操作的均摊复杂度接近常数。
public final class SortedArrayDeduplicator {
private SortedArrayDeduplicator() {
}
public static int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int slow = 0;
// fast 只向右移动一次；slow 也从不回退
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
nums[++slow] = nums[fast];
}
}
return slow + 1;
}
}
// 时间 O(n)，额外空间 O(1)不要因为循环体中有两个指针就判断为 O(n²)。关键是统计每条语句在整个执行过程中最多发生多少次。
空间复杂度与递归栈空间复杂度与递归栈
空间复杂度通常分析相对输入规模新增的辅助空间，不把输入和返回结果本身重复计算，但应主动说明口径。空间复杂度通常分析相对输入规模新增的辅助空间，不把输入和返回结果本身重复计算，但应主动说明口径。
额外数据结构额外数据结构
长度为 n 的哈希表、前缀和数组或 visited 数组都是 O(n) 辅助空间。长度为 n 的哈希表、前缀和数组或 visited 数组都是 O(n) 辅助空间。
递归调用栈递归调用栈
递归深度为 h，就会占用 O(h) 栈空间；退化二叉树的 DFS 深度可能达到 O(n)。递归深度为 h，就会占用 O(h) 栈空间；退化二叉树的 DFS 深度可能达到 O(n)。
原地算法原地算法
O(1) 额外空间不等于完全不分配内存，而是额外空间不随 n 增长。O(1) 额外空间不等于完全不分配内存，而是额外空间不随 n 增长。
输出空间输出空间
生成全部排列本身需要 O(n · n!) 输出；分析辅助空间时应与输出规模分开说明。生成全部排列本身需要 O(n · n!) 输出；分析辅助空间时应与输出规模分开说明。
常见误区
看到两层循环就写 O(n²)看到两层循环就写 O(n²)
先判断内层指针是否会重置。滑动窗口、单调栈中的 while 总执行次数可能只有 O(n)。先判断内层指针是否会重置。滑动窗口、单调栈中的 while 总执行次数可能只有 O(n)。
把哈希表操作无条件当作 O(1)把哈希表操作无条件当作 O(1)
应说明这是平均复杂度；最坏情况与哈希冲突、扩容实现有关。应说明这是平均复杂度；最坏情况与哈希冲突、扩容实现有关。
忽略 Java 标准库的真实成本忽略 Java 标准库的真实成本
Arrays.sort(int[]) 是双轴快速排序，平均 O(n log n)；List.subList 是视图而非复制；String.substring 在现代 JDK 中会复制字符数据。Arrays.sort(int[]) 是双轴快速排序，平均 O(n log n)；List.subList 是视图而非复制；String.substring 在现代 JDK 中会复制字符数据。
递归只算时间，不算栈空间递归只算时间，不算栈空间
递归深度可能触发栈溢出，也是空间复杂度的重要部分。递归深度可能触发栈溢出，也是空间复杂度的重要部分。
面试追问延伸思考
为什么二分查找是 O(log n)？为什么二分查找是 O(log n)？
每轮比较后搜索区间至少缩小一半。执行 k 轮后剩余规模为 n / 2ᵏ，当它降到 1 时，k = log₂n，因此是 O(log n)。每轮比较后搜索区间至少缩小一半。执行 k 轮后剩余规模为 n / 2ᵏ，当它降到 1 时，k = log₂n，因此是 O(log n)。
ArrayList.add 为什么是均摊 O(1)？ArrayList.add 为什么是均摊 O(1)？
扩容虽需 O(n) 复制，但容量按比例增长时，插入 n 个元素产生的总复制量仍是 O(n)，所以平均到每次 add 为 O(1)。单次最坏复杂度仍是 O(n)。扩容虽需 O(n) 复制，但容量按比例增长时，插入 n 个元素产生的总复制量仍是 O(n)，所以平均到每次 add 为 O(1)。单次最坏复杂度仍是 O(n)。
如何分析递归算法复杂度？如何分析递归算法复杂度？
先写出递推式，再看递归树的层数和每层工作量。例如归并排序 T(n)=2T(n/2)+O(n)，共有 O(log n) 层，每层 O(n)，所以是 O(n log n)。先写出递推式，再看递归树的层数和每层工作量。例如归并排序 T(n)=2T(n/2)+O(n)，共有 O(log n) 层，每层 O(n)，所以是 O(n log n)。