算法复杂度
算法复杂度描述的是输入规模变大时,算法的时间和空间开销按什么趋势增长。它通常用 Big-O 记号 O(...) 表示,意思是规模增长时成本的上界;常数和低阶项被省略,只保留增长最快的那一项,比如 3n²+5n 记作 O(n²)。
现场编码时,复杂度有两个用处:动手前,根据题目给的输入上限排除注定超时的方案;写完后,说清楚自己的代码为什么是这个复杂度。Big-O 只描述增长趋势,同样是 O(n) 的两段 Java 代码,装箱、对象分配和数值溢出仍可能让它们的耗时甚至结果完全不同。
1. 面试核心
先记住这几条,再读正文- 时间复杂度按实际执行的操作次数累计,不看循环写了几层;各自只向前移动的双指针总共只移动 O(n) 次。
- 归并排序每层合计处理 O(n) 个元素,共 O(log n) 层,所以总时间是 O(n log n)。卡 · 递归
- 辅助空间统计的是运行中额外存储的峰值,包括同时存活的状态和递归调用栈,而不是历史分配量的总和。
- Big-O 省略了常数,装箱、对象分配和数据访问方式仍会影响 Java 代码的实际耗时。卡 · Java 中的实际成本
- 两个
int的算术运算先按int计算,结果在赋给long之前就可能已经溢出。卡 · 数值范围
2. 输入规模
输入规模是复杂度公式里那个变量所代表的数量。分析之前要先说清楚 n 指的是什么,不同输入要保留的规模不一样:
- 数组使用元素个数 n。
- 字符串需要约定按 Unicode 码点、UTF-16 编码单元还是字节计数。
- 图使用顶点数 V 与边数 E。
- 矩阵同时保留行数 m 和列数 n。
- 多个字符串的排序需要关注字符串数量与总字符数。
比如一百万个短字符串和一个总长一百万的字符串,对象数量和访问方式完全不同,只说「输入长度是一百万」,没法估算内存和遍历成本。
有两个独立输入时,两个规模都要保留。长度分别是 n 和 m 的两个数组,各扫一遍是 O(n+m),枚举所有配对是 O(nm)。如果统一写成 n,n=10、m=一百万 这种悬殊的情况就看不出来了。
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 个元素比较一次,累计就是 n² 次。如果第 i 轮内循环只走 i 次,就要求和:1+2+…+n=n(n+1)/2,省略常数和低阶项后仍是 O(n²)。
5.2 嵌套循环与双指针
循环嵌套不等于 O(n²)。双指针代码常写成两层循环,判断关键是内层指针会不会每轮重置:如果它保留上一轮的位置,两个指针各自最多前进 n 次,累计最多 2n 步。只要每步是 O(1),总成本就是 O(n)。实现和排除候选的依据见双指针。
5.3 递归
分析递归要同时看两件事:每次分出几个子问题,子问题的规模缩小了多少。
归并排序的递推式是 T(n)=2T(n/2)+O(n):T(n) 是处理 n 个元素的时间,两个子调用各处理一半,合并时处理全部 n 个元素。把递归展开成一棵树来看,每一层所有子问题加起来正好处理 n 个元素,也就是 O(n);规模每层减半,一共 O(log n) 层,所以总时间是 O(n log n)。
二分查找每次只进入一个半区,每层做 O(1) 的工作,共 O(log n) 层,时间就是 O(log n)。可见一个函数里有两次递归调用,并不能直接推出指数时间,还要看规模缩得多快、子问题有没有重复计算。递归的调用次数和调用栈深度要分开统计,具体见递归。
6. 空间复杂度
空间复杂度同样要先讲口径。本文把输入和必须返回的输出单独列出,辅助空间只统计算法运行中额外需要、同时存在的最大存储量,也就是峰值。
估算时可以按存储的种类分别算:
- 固定数量的迭代变量占 O(1)。
- 长度为 n 的辅助数组占 O(n)。
- 深度为 h 的递归调用栈占 O(h)。
- 广度优先搜索(BFS)逐层访问节点,队列在最宽时可保存 O(V) 个顶点。
以归并排序为例,使用一个共享缓冲区时,缓冲区占 O(n),递归栈占 O(log n),总辅助空间由 O(n) 主导。即使实现里每层都新建过临时数组,也只按同时存活的数组计算,而不是把所有分配过的数组加起来。
到了 Java 里还要多想一层:失去引用的对象可以被垃圾回收器(GC)回收,但真正释放要等 GC 运行,所以算法所需的空间和 JVM 实际的内存峰值不是一回事。另外,快速排序这类原地划分的算法虽然不新建数组,递归调用栈仍然占空间,也要算进去。
7. Java 中的实际成本
Big-O 省略了常数,可 Java 里每一步访问或计算的实际成本差别很大。两个方案数量级相同时,决定快慢的往往是下面这几类开销。
7.1 基本类型与装箱
int[] 里直接存数值,List<Integer> 里存的是 Integer 对象的引用。把 int 转成 Integer 叫装箱,装箱后每次读取数值都要先通过引用找到包装对象;至于会不会新建对象,还受 Integer 缓存和 JIT 优化的影响。
两者遍历都是 O(n),但后者多了引用访问和包装对象,实际更慢。数值密集的计算可以用基本类型数组,或者 IntStream、LongStream,避免逐个装箱。比如 Arrays.stream(values).asLongStream().sum() 把 int 数组按 long 累加,全程都是基本类型。
7.2 连续内存与节点对象
访问顺序会影响 CPU 缓存的命中率。ArrayList 遍历的是一个引用数组的相邻槽位,访问是连续的;LinkedList 要顺着节点的链接一个个跳,每个元素还额外占一个节点对象和前后链接。
两者遍历都是 O(n),但缓存命中和节点访问的成本不同。具体差多少,要在目标 JVM 和实际负载下测量。
7.3 哈希与比较函数
复杂度分析常把一次哈希或一次比较算作 O(1),但它们内部可能要扫描很多字符。长度为 k 的字符串第一次计算 hashCode 是 O(k),比较两个长字符串要逐个检查公共前缀。所以用字符串做键时,哈希表的成本除了桶定位,还要加上计算哈希的成本;排序做了 O(n log n) 次比较,总成本也要再乘上每次比较的实际开销。
7.4 分配与 GC
循环里的对象分配要结合对象大小来算。每轮创建一个固定大小的短命对象,只会增加分配量和之后的回收工作,复杂度不变;如果每轮创建的对象越来越大,就会改变复杂度。比如依次创建长度为 1 到 n 的字符串,累计复制的字符数是 O(n²)。
除了分配,分支预测也会影响耗时:CPU 会提前猜测分支的走向,猜错了就要丢掉已经执行的后续指令重新来。这类开销很难靠读代码判断,所以优化之前,先用剖析工具或 JMH 找到真正耗时的部分,再决定要不要复用缓冲区、调整数据布局。
JMH 是 OpenJDK 提供的 JVM 微基准测试工具。用它测量时要注意三点:先预热,让 JIT 编译后的代码参与比较;使用计算结果,防止计算被当成无用代码优化掉;运行多轮,观察波动。端到端延迟要单独测,只在代码前后各取一次时间,结果很容易被预热和 GC 干扰。
8. 数值范围
选数值类型时,要保证它装得下所有中间结果,而不只是最终返回值。Java 的 int 运算按 32 位进行,溢出时只保留低 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
width * height 的两个操作数都是 int,乘法按 int 执行,25 亿超出了 int 的上限,所以 wrong 得到负数。(long) width * height 先把一个操作数转成 long,乘法就按 long 执行,area 才是正确结果。计数、距离、累加和、乘积都要按输入上限估算会不会溢出,long 也有上限。需要在溢出时报错,可以用 Math.addExact、Math.multiplyExact,它们溢出时抛出 ArithmeticException。
同样的问题出现在二分查找的中点上。数组下标非负时,写成 left+(right-left)/2 可以避免 left+right 溢出。如果二分的范围覆盖整个 int,right-left 本身也会溢出,要先转成 long 再相减。比较器也一样,用 Integer.compare 而不是 a - b,因为相减可能溢出、让符号反过来,排序结果就错了。
9. 常见问题
9.1 O(1) 就是很快吗?
不一定。O(1) 只说明成本的上界和输入规模无关,一次操作里仍可能有很多步骤,常数大小直接影响实际延迟。
9.2 O(n log n) 一定比 O(n²) 快吗?
规模足够大时是这样,因为 n log n 增长得更慢。输入很小时,常数和数据访问成本可能让 O(n²) 的实现反而更快。要比较两个具体实现,就在目标规模下测量。
9.3 返回结果占用的空间算不算空间复杂度?
要分开报告。返回 n 个元素的列表需要 O(n) 的输出空间;除了输出只用了几个变量的话,辅助空间是 O(1)。只说一个数,读者分不清你算的是哪一个。
9.4 Stream 操作链的复杂度怎么算?
看真正执行了哪些操作。map、filter 是一次扫描,sorted 要排序,成本不同;同样的遍历用 Stream 写还是用循环写,增长趋势不变。
除了增长趋势,还要留意这些实际开销:
- 装箱和临时对象会增加分配开销。
- 短路操作在得到答案后提前结束,会减少实际访问的元素。
- 有状态操作需要保留中间结果,sorted 还需要排序。
- 并行执行增加任务调度与结果合并的成本。
10. 面试题卡片
11. 参考资料
- Java SE 21:Arrays
- Java SE 21:Integer.compare
- OpenJDK:JMH
- Java SE 21 JLS:Integer Operations
- Princeton Algorithms:Mergesort
来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明