复杂度、约束与 Java 成本模型
算法复杂度描述输入规模增长时，时间和额外空间怎样增长。面试和工程实现都应先从输入约束排除不可行方案，再把 Java 中的对象、装箱、哈希和递归成本放回分析。
1. 先定义输入规模
复杂度中的 n 必须对应具体数量：
- 数组题：元素个数。
- 字符串题：UTF-16 code unit 数、Unicode code point 数或字节数。
- 图问题：顶点数
V与边数E。 - 矩阵问题：行数
m与列数n。 - 排序多个字符串：字符串数量与总字符数。
只写 O(n) 而不说明 n 是什么，无法判断真实资源。遍历一个有一百万个短字符串的列表，与遍历一个总长度一百万的单字符串，内存访问和对象数量都不同。
2. 约束先决定可接受数量级
假设单机算法时间上限大致固定，可以用数量级快速排除：
| 输入规模 | 通常优先考虑 |
|---|---|
n <= 20 | 子集枚举、指数搜索加剪枝 |
n <= 1,000 | O(n²) 可能可行 |
n <= 100,000 | O(n log n) 或 O(n) |
n 达到千万 | 单次线性扫描也要关注常数、I/O 与内存 |
这不是运行时承诺。元素操作成本、时间限制、语言和硬件都会改变边界。它的作用是帮助提问：数据能否放进内存、是否已排序、值域多大、允许近似吗、需要在线处理吗。
3. 最坏、平均与摊销复杂度
三种描述回答不同问题：
- 最坏复杂度：任意合法输入的上界。
- 平均复杂度：依赖输入分布假设。
- 摊销复杂度：一串操作的总成本平均到每次操作。
HashMap 查找平均接近 O(1)，但冲突分布决定桶内路径；ArrayList 尾部追加摊销 O(1)，某次扩容仍需 O(n) 复制。
面试中需要说明使用哪一种。如果系统面对恶意输入，平均复杂度的分布假设可能不成立，应同时考虑最坏路径与输入限额。
4. 时间复杂度从执行次数推导
4.1 连续循环相加，嵌套循环相乘
for (int value : values) {
inspect(value);
}
for (int value : values) {
persist(value);
}
总次数是 n + n，忽略常数后为 O(n)。
for (int left : values) {
for (int right : values) {
compare(left, right);
}
}
每个外层元素都遍历 n 个内层元素，总次数约 n²。
4.2 双重语法不一定是 O(n²)
双指针中，每个指针都只向前移动：
while (right < values.length) {
add(values[right++]);
while (windowInvalid()) {
remove(values[left++]);
}
}
虽然循环嵌套，left 和 right 各最多移动 n 次，总成本仍为 O(n)。分析应计算状态总共变化多少次，不能只数大括号层数。
4.3 递归看调用树
二分查找每次把规模减半，深度 O(log n)。归并排序每层处理 O(n)，共有 O(log n) 层，所以时间 O(n log n)。有两个递归调用不自动等于 O(2ⁿ)，还要看子问题规模和是否重复计算。
5. 空间复杂度看同时存活的额外状态
空间复杂度通常统计除输入和必要输出之外的峰值额外空间：
- 迭代变量 O(1)。
- 长度 n 的辅助数组 O(n)。
- 递归深度 h 的调用栈 O(h)。
- BFS 队列最宽可能 O(V)。
归并排序每层都创建临时数组时，不应机械把所有递归层的数组大小相加。要看它们是否同时存活、何时可回收。Java 中对象“可以被 GC”不等于已经立即释放，实际峰值还受分配时机和实现方式影响。
原地算法也可能使用递归栈，因此“没有 new 数组”不一定是 O(1) 空间。
6. Big-O 相同，Java 成本仍可能不同
6.1 基本类型与装箱
int[] 连续保存数值，List<Integer> 保存引用并可能产生 Integer 对象。两者都能 O(n) 遍历，后者的内存、间接访问和装箱成本通常更高。
long sum = Arrays.stream(values).asLongStream().sum();
数值密集路径使用基本类型数组和 IntStream、LongStream 可以减少装箱。
6.2 连续内存与节点对象
ArrayList 和 LinkedList 遍历都是 O(n)，引用数组通常有更好的缓存局部性；链表为每个元素增加节点和链接。
6.3 哈希与比较函数
HashMap 操作的平均桶定位接近 O(1)，但 key 的 hashCode 可能本身是 O(k)。排序 O(n log n) 次比较，如果 Comparator 扫描长字符串，总成本还要乘上比较代价。
6.4 分配与 GC
循环中创建大量短命对象不会改变渐进复杂度，却可能增加分配速率和 GC。先用剖析或 JMH 证明热点，再决定是否复用缓冲、改用基本类型或调整数据布局。
7. 数值范围也是算法约束
int middle = (left + right) / 2;
left + right 可能溢出。二分中写：
int middle = left + (right - left) / 2;
计数、距离和乘积也要估算最大值。两个 int 相乘后再赋给 long，溢出已经发生：
long area = (long) width * height;
Comparator 不要写 left.score() - right.score()，差值可能溢出；使用 Integer.compare。
8. 常见问题
8.1 O(1) 是否表示只执行一步
不是。它表示执行次数不随输入规模增长，可以包含固定数量的多步操作。常数仍会影响实际延迟，只是在增长分析中省略。
8.2 O(n log n) 一定比 O(n²) 快吗
当 n 足够大且基本操作可比较时，增长更慢；小输入、昂贵常数和缓存行为可能让结果相反。复杂度用于判断扩展趋势，基准用于判断具体实现。
8.3 输出本身有 O(n) 大小，空间复杂度怎么算
要说明口径。通常把必要输出空间单独列出，再报告算法额外空间。例如返回 n 个元素的列表需要 O(n) 输出，算法除输出外可能只用 O(1) 辅助状态。
8.4 Stream 会改变复杂度吗
同样的遍历和数据结构通常保持相同渐进复杂度，但中间有状态操作、装箱、对象分配和并行调度会改变常数甚至算法路径。应分析实际操作链，不能按语法风格下结论。
9. 面试题
9.1 归并排序的时间和空间复杂度怎样推导
出现公司：字节跳动
考察重点
- 递归层数与每层合并工作的乘积。
- 同时存活空间与累计分配量的区别。
- Java GC 不会改变算法峰值空间口径。
相关内容：第 4 节“时间复杂度从执行次数推导”、第 5 节“空间复杂度看同时存活的额外状态”。
参考回答
归并排序把数组不断对半分，共 O(log n) 层；每层合并总共处理 n 个元素，所以时间是 O(n log n)。典型数组实现需要长度 O(n) 的辅助存储，递归栈是 O(log n)，峰值额外空间由 O(n) 主导。
不能因为每层都执行过合并就把临时空间简单累加成 O(n log n)，空间复杂度看同时存活的峰值；也不能因为 Java 最终会 GC 就忽略仍在当前调用链中可达的缓冲。
9.2 为什么两个 O(n) 的 Java 实现性能可能差很多
出现公司：腾讯、阿里巴巴、美团、快手、字节跳动
考察重点
- Big-O 忽略常数与数据布局。
- 装箱、对象分配、缓存局部性和函数成本。
- 怎样用剖析和基准验证。
相关内容：第 6 节“Big-O 相同，Java 成本仍可能不同”。
参考回答
O(n) 只说明工作量随 n 线性增长，不说明每一步成本。int[] 与 List<Integer> 都是线性遍历，但后者包含引用访问和可能的装箱对象；连续数组与链表节点的缓存局部性也不同。
此外，哈希和比较函数、临时对象分配、分支预测和 GC 都会改变常数。先用复杂度排除数量级不合适的方案，再用 JMH 或端到端剖析比较目标负载，不能用一次墙钟计时代替分析。