算法复杂度

算法复杂度描述输入规模增长时，时间和空间开销怎样增长。本文先从题目约束估算操作量，再推导循环、递归与峰值空间。最后结合 Java 的对象分配和数值范围，说明实现时还要计算哪些成本。

文中的 O(...) 称为 Big-O 记号，表示规模增长时的成本上界。它省略常数和较低阶项，便于比较增长趋势。

1. 面试核心

先记住这几条，再读正文

• 操作次数。 嵌套循环的时间复杂度要按实际执行次数累计，而各自只向前移动的双指针总共移动 O(n) 次。
• 分层求和。 归并排序每层处理 O(n) 个元素，共有 O(log n) 层，因此总时间复杂度为 O(n log n)。卡 · 递归
• 辅助空间。 辅助空间复杂度统计算法运行时额外存储的峰值，包括同时存活的状态和递归调用栈。
• 实际执行成本。 Big-O 省略了常数因子，Java 实现中的装箱、对象分配和数据访问仍会影响实际耗时。卡 · Java 中的实际成本
• 整数提升。 两个 int 的算术运算先按 int 计算，因此结果在赋值给 long 之前就可能溢出。卡 · 数值范围

2. 输入规模

分析复杂度前，要先说清变量对应什么数量。不同问题需要保留不同的输入规模：

• 数组使用元素个数 n。
• 字符串需要约定按 Unicode 码点、UTF-16 编码单元还是字节计数。
• 图使用顶点数 V 与边数 E。
• 矩阵同时保留行数 m 和列数 n。
• 多个字符串的排序需要关注字符串数量与总字符数。

比如，一百万个短字符串与总长一百万的单个字符串，对象数量和访问方式都不同。因此，只说“输入长度是一百万”，还不足以估算内存与遍历成本。

两个独立输入长度为 n、m 时，共同扫描为 O(n+m)。枚举所有配对为 O(nm)。用一个 n 替代两者会隐藏规模差异。

3. 由约束估算数量级

输入上限能帮助排除工作量过大的方案。先估算操作次数，再结合时限和单步成本判断是否可行：

规模示例	操作量
n=20	2ⁿ 约一百万，枚举还需计算每项成本。
n=1000	n² 为一百万。
n=100000	n² 为一百亿，n log₂ n 约一百七十万。
n=10000000	一次扫描已有一千万项，需估算内存与 I/O。

由这些操作量，可以得到初步选择方向：

• n 在 20 以内时，可以估算子集枚举或指数搜索加剪枝的成本。
• n 在 1000 左右时，可以考虑 O(n²)，再核算每次操作的成本。
• n 达到 100000 时，应优先考虑 O(n log n) 或 O(n)。
• n 达到千万时，即使只扫描一次，也要关注内存、I/O 和常数开销。

这些规模只用于估算，具体边界取决于语言、硬件和题目时限。选择方案前，还应确认以下约束：

• 数据能否全部放进内存，输出量有多大？
• 输入是否已排序，元素值域有多大？
• 答案是否允许近似？
• 数据是否逐条到达，并要求随到随处理，也就是在线处理？

规模估算用于排除方案，具体耗时则需要测量。

4. 最坏、平均与摊销复杂度

报告复杂度时，需要说明采用哪一种口径。它们分别回答以下三个问题：

• 最坏复杂度：在所有合法输入中，成本上界是多少？
• 平均复杂度：按给定的输入分布取平均，成本是多少？期望成本也可以来自算法自身的随机选择。
• 摊销复杂度：一串操作的总成本平均到每次操作是多少？这里无需假设输入随机。

比如，ArrayList 尾部追加的摊销成本为 O(1)，但某次扩容仍需复制 O(n) 项，证明见数组。

HashMap 查找在哈希分布合适时接近 O(1)，冲突增多会增加桶内查找成本，条件见哈希表。

如果输入由外部用户控制，还要考虑恶意构造的冲突或极端规模。此时平均分布假设会失效，所以需要结合最坏路径设置输入限额。

5. 时间复杂度推导

必会卡 · 归并排序的时间与空间如何推导？

时间复杂度取决于实际执行的操作总量。本节先看循环怎样累计，再用递归树解释分治算法。

5.1 连续循环与嵌套循环

连续循环将各段成本相加，嵌套循环则要看内层实际执行多少次。比如，先对每项执行 inspect，再对每项执行 persist。若两个操作都是 O(1)，两个顺序扫描共执行 2n 次操作，时间为 O(n)。

若每个外层元素都与全部 n 个元素比较一次，且每次比较为 O(1)，累计就是 n² 次操作。

若第 i 轮内循环只走 i 次，则需求和。1+2+…+n=n(n+1)/2，仍为 O(n²)。

5.2 嵌套循环与双指针

分析双指针时，关键是检查内层指针是否保留上轮位置。两个单向指针各自最多前进 n 次，累计最多走 2n 步。所以，即使写成嵌套循环，只要单步为 O(1)，总成本仍为 O(n)。

实现与排除依据见双指针。

5.3 递归

递归需要同时看子问题数量与子问题规模。比如，归并排序的递推式为 T(n)=2T(n/2)+O(n)。T(n) 表示处理 n 项的时间，两个子调用各处理一半，合并处理全部 n 项。

每层所有子问题合计处理 O(n) 项。规模不断减半，共 O(log n) 层，所以总时间为 O(n log n)。二分查找每次只访问一个半区，每层做 O(1) 工作，时间就是 O(log n)。因此，两个递归调用本身不足以推出指数时间，还要看规模缩减和重复计算。

调用次数与活动深度分开统计，具体见递归。

6. 空间复杂度

必会卡 · 归并排序的时间与空间如何推导？

空间复杂度需要说明统计口径。本文将输入与必要输出单独列出，辅助空间统计运行中同时需要的最大存储量，也就是峰值。

估算时，可以按以下几类存储分别计算：

• 固定数量的迭代变量占 O(1)。
• 长度为 n 的辅助数组占 O(n)。
• 深度为 h 的递归调用栈占 O(h)。
• 广度优先搜索（BFS）逐层访问节点，队列在最宽时可保存 O(V) 个顶点。

归并排序使用一个共享缓冲区时，辅助数组占 O(n)，递归栈占 O(log n)。因此，总辅助空间由 O(n) 主导。即使每层都创建过临时数组，也要按同时存活的数组统计，而不是累加历史分配量。

Java 中失去引用的对象可以被垃圾回收器（GC）回收，但释放发生在实际回收时。仍被当前调用引用的缓冲区需要保留，所以要区分算法所需空间与 JVM 的实际内存峰值。原地划分同样会保存递归调用状态，即使没有新数组，也需计算调用栈。

7. Java 中的实际成本

必会卡 · 两个 O(n) 的 Java 实现为何耗时不同？

Big-O 省略了常数，而 Java 中每次访问或计算的成本会随实现变化。比较相同数量级的方案时，还需要检查以下几类开销。

7.1 基本类型与装箱

数值遍历首先要区分直接存值和保存对象引用。int[] 保存数值，List<Integer> 保存 Integer 对象的引用。将 int 转成 Integer 称为装箱，它引入包装对象访问，是否新建对象还受缓存与优化影响。

两者都可以 O(n) 遍历，但引用访问和包装对象会增加实际成本。数值密集的计算可使用基本类型数组，或 IntStream、LongStream，减少逐项装箱。比如，Arrays.stream(values).asLongStream().sum() 按 long 累加 int 数组，元素仍以基本类型处理。

7.2 连续内存与节点对象

访问顺序会影响 CPU 缓存的利用率。ArrayList 遍历引用数组的相邻槽位，具有连续访问的局部性。LinkedList 则逐个跟随节点链接，每项还需要额外的节点和链接存储。

两者遍历都为 O(n)，但缓存命中与节点访问成本不同。具体差距需要在目标 JVM 和负载下测量。

7.3 哈希与比较函数

调用一次哈希或比较函数，内部仍可能扫描许多字符。长度为 k 的字符串首次计算哈希需 O(k)，比较两个长字符串则需要检查公共前缀。因此，哈希表的桶定位成本之外，还要算上键的哈希成本。执行 O(n log n) 次比较的排序，也需乘上实际比较成本。

7.4 分配与 GC

循环中的对象分配需要结合对象大小计算。每轮创建固定大小的短命对象，会增加分配量和后续回收工作。若每轮创建的结果越来越长，还会改变渐近复杂度。比如，依次复制 1 到 n 个字符，累计复制量为 O(n²)。

优化前应先用剖析工具或 JMH 找到耗时集中的部分，再决定是否复用缓冲区或调整数据布局。分支预测也会影响耗时：CPU 对分支走向判断错误时，需要重新执行后续指令。

JMH 是用于 JVM 的微基准工具。测量时需要预热，让即时编译后的代码参与比较。还要使用计算结果，避免计算被优化掉，并运行多轮比较波动。端到端延迟则需单独测量，一次简单计时容易受预热和 GC 干扰。

8. 数值范围

必会卡 · 为什么 int 相乘赋给 long 仍会溢出？

数值类型要覆盖中间结果，而不只覆盖最终返回值。Java 21 的 int 算术按 32 位执行，溢出时保留低位。赋给 long 时，扩宽的是已经算出的结果：

int width = 50_000, height = 50_000;
long wrong = width * height;
long area = (long) width * height;
System.out.println(wrong); // -1794967296
System.out.println(area);  // 2500000000

示例中，int 乘法已经溢出，所以 wrong 得到负数。先提升一个操作数，乘法才按 long 执行，area 因而得到正确结果。计数、距离、累加和乘积都需要按输入上界估算，long 也有范围限制。需要检测溢出时，可使用 Math.addExact 或 Math.multiplyExact。

非负数组下标的中点可写 left+(right-left)/2，避免 left+right 溢出。若二分覆盖整个 int 范围，right-left 也会溢出，需要在相减前提升为 long。比较器用 Integer.compare，避免以差值的符号判断顺序时受溢出影响。

9. 常见问题

下面区分增长趋势与实际速度，并说明输出和 Stream 操作链的统计方式。

9.1 常数时间

O(1) 表示成本上界与所选输入规模无关。一次操作仍能包含多个步骤，常数会影响实际延迟。

9.2 渐近增长与实际速度

9.3 输出空间

9.4 Stream 操作链

10 · 面试题卡片

先想答案，再翻面先在心里答一遍，再点开卡片对照参考回答。卡片之间可以左右切换，看完会回到这里。

逐张翻看 3 张 →

递归必会

归并排序的时间与空间如何推导？

字节跳动

考察 1 点 · 相关 §5.3 §6

Java 中的实际成本必会

两个 O(n) 的 Java 实现为何耗时不同？

腾讯阿里巴巴美团快手字节跳动

考察 1 点 · 相关 §7

数值范围必会

为什么 int 相乘赋给 long 仍会溢出？

本站自测

考察 1 点 · 相关 §8

本页题目与参考回答

10.1 归并排序的时间与空间如何推导？

出现公司：字节跳动

考察重点：解释递归层数与每层合并成本，并区分同时存活的空间和累计分配量。

相关内容：递归、空间复杂度。

参考回答

标准数组归并排序的时间为 O(n log n)，辅助空间为 O(n)。

数组不断对半分，递归共有 O(log n) 层。每层合并的元素总数为 n，所以各层工作相加为 O(n log n)。共享缓冲区占 O(n)，同时活动的调用栈占 O(log n)，空间由前者主导。

空间统计的是同时存活的峰值，历史上执行过的合并无需逐层累加。Java 的 GC 会影响实际释放时机，当前调用仍引用的缓冲区则始终需要计入。

10.2 两个 O(n) 的 Java 实现为何耗时不同？

出现公司：腾讯、阿里巴巴、美团、快手、字节跳动

考察重点：解释单步成本和数据布局怎样影响耗时，并说明怎样通过剖析与基准验证。

相关内容：Java 中的实际成本。

参考回答

Big-O 忽略常数，所以同为 O(n) 的代码，每一步的实际成本仍可不同。

比如，int[] 直接访问数值，List<Integer> 还要读取对象引用。数组与链表的缓存局部性也不同。除此之外，还需比较以下开销：

• 哈希和比较函数内部做了多少计算。
• 装箱、临时对象分配和 GC 花费多少时间。
• 分支预测是否频繁失败。

应在相同输入和 JVM 条件下，用 JMH 或端到端剖析测量。控制预热、使用计算结果并运行多轮后，比较才有意义。

10.3 为什么 int 相乘赋给 long 仍会溢出？

出现公司：暂无已核验的公开来源（本站自测）

考察重点：说明操作数类型怎样决定乘法类型，以及类型转换发生在运算前后有什么区别。

相关内容：数值范围。

参考回答

因为两个操作数都是 int，乘法会先按 int 计算，再将结果赋给 long。

溢出发生在乘法阶段，随后转成 long 也无法恢复丢失的高位。写成 (long)width*height，就会先提升操作数，再按 long 相乘。最终还需确认乘积处于 long 范围内。

11. 参考资料

• Java SE 21：Arrays
• Java SE 21：Integer.compare
• OpenJDK：JMH
• Java SE 21 JLS：Integer Operations
• Princeton Algorithms：Mergesort