外观
01 - 代码能跑不等于能用:时间复杂度如何决定系统上限
示例环境:Java 17。复杂度结论与语言版本无关;实际耗时受硬件、JVM、数据分布和实现方式影响。
后续验证方法:A - 算法正确性、测试与基准方法。
摘要
处理 1,000 条数据很快的代码,处理 100 万条时为什么可能超时?关键在于工作量随数据规模增长的速度。本文先用重复订单检测说明如何统计操作次数,再解释时间复杂度、空间复杂度和不同分析条件,最后结合性能测量与资源约束选择方案。
1. 场景引入:测试环境 8 毫秒,线上为什么超时
一个订单导入接口需要检查批次中是否存在重复订单号。第一版让每个订单号与它后面的订单号逐一比较,发现相同值就返回:
以下方法片段假设数组和订单号都非 null。后文的重复检测对比也使用这一输入约束,避免不同实现对 null 的处理影响比较。
java
public static boolean hasDuplicate(String[] orderIds) {
for (int i = 0; i < orderIds.length; i++) {
for (int j = i + 1; j < orderIds.length; j++) {
if (orderIds[i].equals(orderIds[j])) {
return true;
}
}
}
return false;
}测试环境每批只有 1,000 条订单,运行很快。某次迁移任务一次导入 100 万条,接口长时间没有返回,CPU 使用率持续升高。
小批次的单次耗时不能直接用于预测大批次容量。耗时还受硬件、JVM、输入分布和测量方法影响;判断规模扩大后的风险,应先看比较次数如何增长。
代码没有死循环,也没有锁等待。问题在于数据规模放大后,需要执行的比较次数增长得太快。
假设所有订单号都不重复,代码会完成全部比较:
text
(n - 1) + (n - 2) + ... + 1
= n × (n - 1) / 2当 n = 1,000 时,大约比较 50 万次;当 n = 1,000,000 时,大约比较 5,000 亿次。输入扩大 1,000 倍,工作量不是扩大 1,000 倍,而是接近扩大 100 万倍。
在单次比较成本接近、其他条件相近时,比较次数越多,所需 CPU 工作量就越大。如果单个批次长期占用处理资源,其他请求还可能排队。因此,小数据上的快速返回不能证明算法能支撑大批次。
2. 时间复杂度描述的不是秒数
**时间复杂度(Time Complexity)**描述算法工作量如何随输入规模增长。分析时先定义输入规模 n,再统计核心操作次数 T(n),最后用大 O 表示法(Big O notation)概括增长上界:当 n 足够大时,工作量不超过某个增长函数的常数倍。
它不直接回答“运行需要多少毫秒”,而是回答:
当输入规模
n增长时,执行步骤大致以什么速度增长?
下面按典型增长函数比较趋势,表中的倍数不是实测耗时比。Hash(哈希)表根据键的哈希值定位存储位置,以减少逐项查找;其平均复杂度有成立条件,第 5 节再展开。表中的动态规划(DP)是通过保存子问题结果来避免重复求解的方法,具体分析还需统计状态数量和每个状态的处理成本。
| 复杂度 | n 扩大 10 倍后的增长趋势 | 常见场景 |
|---|---|---|
O(1) | 基本不随 n 增长 | 数组按下标访问、Hash 表平均查找 |
O(log n) | 增长很慢 | 二分查找、平衡树查找 |
O(n) | 约 10 倍 | 顺序扫描 |
O(n log n) | 略高于 10 倍 | 高效通用排序 |
O(n²) | 约 100 倍 | 两两比较、部分二维动态规划(DP) |
O(2ⁿ) | 指数增长 | 未剪枝的子集搜索 |
O(n!) | 增长极快 | 枚举所有排列 |
大 O 关注增长趋势,会忽略常数倍和低阶项。例如:
text
T(n) = 3n² + 20n + 100当 n 足够大时,n² 主导增长,因此记作 O(n²)。
这里统计的是工作量,不是秒数。即使两个实现都只扫描一次数组,每个元素做一次整数比较与每次发送网络请求,耗时也可能相差很大。只有把单次操作成本近似视为固定,操作次数才能帮助估计耗时增长;真实性能仍要测量。
3. 如何一步步分析一段代码
3.1 先定义输入规模
n 必须有明确含义:
- 数组长度;
- 图的顶点数
V和边数E; - 字符串长度;
- 矩阵行数和列数;
- 一批请求或记录的数量。
如果一个算法处理两个独立数组,长度分别为 m 和 n,复杂度可能是 O(m + n) 或 O(mn),不能为了简洁都写成 O(n)。
3.2 找出随输入增长的核心操作
java
public static int max(int[] values) {
int result = values[0];
for (int i = 1; i < values.length; i++) {
if (values[i] > result) {
result = values[i];
}
}
return result;
}此方法要求数组非 null 且至少有一个元素。数组长度为 n 时,比较执行 n - 1 次;整数比较和赋值都按常数成本计,所以总工作量随 n 线性增长,记作 O(n)。
3.3 顺序执行通常相加,嵌套执行通常相乘
java
for (int value : first) {
// m 次
consume(value);
}
for (int value : second) {
// n 次
consume(value);
}若 consume() 每次成本为 O(1),两个循环分别执行 m 次和 n 次,总复杂度是 O(m + n)。这里和下文的 consume()、compare() 都是表示核心操作的占位调用,并非完整程序。
java
for (int left : first) {
// m 次
for (int right : second) {
// 每次 n 次
compare(left, right);
}
}若 compare() 每次成本为 O(1),外层每处理一个元素,内层都完整执行 n 次,共执行 mn 次,总复杂度是 O(mn)。
但“看见嵌套循环就是 O(n²)”并不可靠。
java
for (int i = 1; i < n; i *= 2) {
for (int j = 0; j < n; j++) {
consume(j);
}
}外层的 i 依次取 1、2、4、8……,翻倍约 log₂n 次便达到 n。每轮内层执行 n 次,在 consume() 为常数成本、i *= 2 不发生整数溢出的前提下,整体是 O(n log n)。这是循环计数片段,不能忽略 Java int 的取值范围。
4. 常见复杂度是怎样出现的
4.1 O(1):执行次数不依赖输入规模
java
public static int first(int[] values) {
return values[0];
}此方法同样要求数组非 null 且非空。无论数组有多少元素,都只访问第一个位置,因此是 O(1)。它表示执行次数不随数组长度增长,不表示只执行一条机器指令或耗时一定很小。
4.2 O(log n):每一步排除固定比例的数据
二分查找每次把搜索范围缩小一半:
text
n -> n/2 -> n/4 -> n/8 -> ... -> 1log₂n 表示“把 n 连续减半,需要多少次才能缩小到 1”。例如,规模为 8 时,范围经过 8 → 4 → 2 → 1,缩小 3 次。不同固定底数的对数只差常数倍,所以大 O 中通常写作 O(log n)。
java
public static int binarySearch(int[] sorted, int target) {
int left = 0;
int right = sorted.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (sorted[mid] == target) {
return mid;
}
if (sorted[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}此方法要求数组非 null 且按升序排列,每轮通过大小比较排除一半候选位置;找到时返回下标,找不到时返回 -1。如果为了查找一次先执行 O(n log n) 排序,再做 O(log n) 查找,总成本仍由排序主导,不能只计算最后的查找步骤。
4.3 O(n log n):分层处理,每层扫描全部数据
归并排序先把数组拆成更小的部分,再把各个有序部分合并。不断折半形成约 log n 层;同一层的各个部分合计仍有 n 个元素,合并时每个元素只需处理常数次。于是每层工作量为 O(n),乘以层数得到 O(n log n)。
图表将在阅读到此处时加载…
4.4 O(n²):元素之间进行大范围配对
重复订单检测在没有重复值时,会比较全部 n(n - 1)/2 对订单号。按单次比较成本固定计算,最坏时间复杂度是 O(n²)。
4.5 O(2ⁿ) 与 O(n!):组合搜索空间
如果每个元素都有“选或不选”两种状态,每增加一个元素,选择组合数就翻倍,全部子集共有 2ⁿ 个。排列则依次有 n、n - 1、……、1 种位置选择,共有 n!(阶乘)种。这里说明的是候选数量;若还要复制或检查每个候选,总工作量需再计入这些成本。
剪枝是在逐步构造候选方案时,提前判断当前选择不可能得到合法结果,跳过这一分支后续的全部候选。例如,从一组正数中选择若干个数,使总和等于目标值:如果已选数字之和超过目标,继续加入正数只会让总和更大,因此无需再尝试包含当前选择的后续组合。剪枝必须有依据,确保不会漏掉合法答案;这个例子若允许负数,后续选择可能使总和减小,就不能沿用同一判断。
这类算法并非一定不能用。当 n 很小、剪枝能有效减少候选或业务确实要求精确枚举时,它们仍有价值。不过,剪枝效果依赖输入和规则,不保证改变最坏情况下的增长趋势;要求枚举全部结果时,也必须承担输出这些结果的成本。关键是先确认输入上限,再估算实际需要处理的候选数量。
5. 最好、最坏、平均情况分别意味着什么
同样长度的数组,重复值的位置不同,执行次数也会不同。最好情况取同规模输入中的最小工作量,最坏情况取最大工作量,平均情况则按指定输入分布计算平均工作量。
重复检测的暴力代码中,前两个元素相同就能立即返回,最好情况是 O(1);没有重复则需要完成全部比较,最坏情况是 O(n²)。这里仍按单次订单号比较为常数成本计算。
线上容量评估通常不能只看最好情况。面对外部输入、延迟目标和资源限制,最坏情况往往更有保护价值。
Hash 表查找常被称为平均 O(1),前提包括哈希值分布良好、计算哈希值和判断键相等的成本可按常数计。不同键定位到同一存储桶称为哈希冲突,需要进一步区分这些键;冲突严重时,查找可能退化。Java HashMap 在特定条件下会把长链表转换成树结构,具体阈值和实现属于版本事实,阅读源码时应固定 JDK 版本;自定义 Hash 结构未必具备相同保障。
平均复杂度也不等于“拿几组随机数据测平均耗时”。严格的平均分析需要明确输入分布,而生产输入经常并不随机。
6. 均摊复杂度:偶尔很贵,长期仍然便宜
**均摊分析(Amortized Analysis)**研究一系列操作的总成本,再把成本分摊到每次操作。
动态数组是在底层数组装满时分配更大数组的结构。尾部追加是典型的均摊分析例子:多数 add() 只写入一个元素,少数扩容操作需要申请新数组并复制已有元素。
假设从常数初始容量开始,容量每次翻倍,且只连续尾部追加、不穿插主动缩容。下面用 n 为 2 的幂时的复制序列说明:
text
复制数量:1 + 2 + 4 + 8 + ... + n/2 < n在上述序列中,每项都是前一项的两倍,总复制量小于 n;再加上 n 次写入,总成本仍是 O(n)。其他 n 的取值也保持线性总成本,因此分摊到每次尾部追加是均摊 O(1)。这依赖操作序列和扩容策略,不要求输入随机,也不是对某个 JDK 容器扩容倍数的断言。
均摊 O(1) 不保证每次操作都很快。P99 是第 99 百分位延迟,表示约 99% 的请求延迟不超过该值,用来观察较慢请求。扩容集中复制元素可能使部分请求变慢,低延迟系统仍需预估容量或考虑其他结构。
7. 空间复杂度:时间优化往往要付内存
**空间复杂度(Space Complexity)**描述所需空间如何随输入增长。本文统一讨论额外空间,即不计调用方已提供的输入,计入算法新建的集合、数组和调用栈等。
回到重复订单检测,可以用 HashSet 保存已见过的订单号。它是基于哈希表的集合,同一个值只保留一份;add() 返回 false,就说明这个订单号已经出现过。每次只需检查当前值是否已在集合中,无需反复扫描前面的订单号。具体实现见第 8 节完整程序的 byHash() 方法。
在 Hash 操作平均 O(1) 的假设下:
- 时间复杂度:
O(n); - 额外空间复杂度:
O(n)。
上述结论把订单号的哈希与比较成本视为常数。若订单号长度也随输入增长,需同时考虑字符串长度,不能只统计订单条数。集合最多保存 n 个不同值,因此用额外空间减少了重复比较。
这是典型的空间换时间。如果批次可能包含数亿条记录,全部放入内存可能不可接受,此时需要考虑:
- 外部排序:借助磁盘等外部存储完成排序,再扫描相邻项;
- 数据库唯一约束:由共享存储拒绝指定键的重复写入;
- 分区处理:按订单号把相同值分到同一分区,避免漏掉跨分区重复;
- Bloom Filter(布隆过滤器)预筛加精确存储验证:预筛可能把不存在的值判断为“可能存在”,最终仍需精确判断;
- 从源头保证幂等键唯一:为同一业务操作使用可重复识别的键,并由写入规则约束重复操作。
算法选型不能只追求时间复杂度最低,还要符合内存、延迟和一致性约束。
8. 三种重复检测方案的对比
下面的完整程序展示三种方案,使用 Java 17,类名对应文件名 DuplicateAlgorithmDemo.java。输入包含重复的 A-101,三个方法的预期返回值均为 true。该程序只演示功能,不能用于比较速度,性能测量见第 10 节。
java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/**
* 可运行示例:代码能跑不等于能用:时间复杂度如何决定系统上限。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class DuplicateAlgorithmDemo {
static boolean byPair(String[] values) {
for (int i = 0; i < values.length; i++) {
for (int j = i + 1; j < values.length; j++) {
if (values[i].equals(values[j])) return true;
}
}
return false;
}
static boolean byHash(String[] values) {
Set<String> seen = new HashSet<>();
for (String value : values) {
if (!seen.add(value)) return true;
}
return false;
}
static boolean bySort(String[] values) {
String[] copy = Arrays.copyOf(values, values.length);
Arrays.sort(copy);
for (int i = 1; i < copy.length; i++) {
if (copy[i - 1].equals(copy[i])) return true;
}
return false;
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
String[] values = { "A-100", "A-101", "A-102", "A-101" };
System.out.println("pair = " + byPair(values));
System.out.println("hash = " + byHash(values));
System.out.println("sort = " + bySort(values));
}
}8.1 反例:两两比较
对应上方完整程序的 byPair():每个元素与后面的元素逐一比较,发现重复就返回;全部比较完仍未发现重复,则返回 false。按单次字符串比较为常数成本计算:
- 时间:最坏
O(n²); - 空间:
O(1); - 适合:数据非常小且内存限制严格的简单场景。
- 副作用:不修改输入,也不创建随输入增长的集合或数组。
8.2 正例:HashSet
对应上方完整程序的 byHash():边扫描边把值加入集合,加入失败就返回 true。按哈希值分布良好、字符串哈希与比较成本可视为常数的条件计算:
- 时间:平均
O(n); - 空间:
O(n); - 适合:内存可容纳集合,需要线性扫描。
- 副作用:不修改输入,但会创建集合并保存已见过的值,增加内存占用。
8.3 折中方案:排序后扫描
对应上方完整程序的 bySort():先复制并排序数组,再检查相邻值。相同值排序后会相邻,因此一次扫描就能发现重复。按单次字符串比较为常数成本计算:
- 时间:通常
O(n log n); - 额外空间:取决于复制及排序实现;此处复制数组明确需要
O(n)引用空间; - 适合:需要保留原数组,同时也可能复用排序结果。当前方法只返回布尔值,不向调用方提供排序副本;复用排序结果需要另行设计接口。
- 副作用:只改变副本的顺序,原数组保持不变;复制数组及排序会占用额外内存。
如果允许修改输入,可以省去显式复制,但排序算法自身的额外空间与最坏行为要根据具体类型、JDK 版本和 API 实现确认。
9. 为什么实际性能不能只看 Big O
9.1 常数成本
O(n) 的操作可能包含昂贵的正则表达式、对象分配或网络访问。复杂度相同不代表耗时相同。
9.2 CPU Cache 与内存布局
CPU Cache(处理器缓存)保存近期访问的内存数据,访问缓存通常比访问主内存更快。连续数组通常更利于连续访问,链表则需要沿引用逐个定位节点。即使遍历都是 O(n),单位时间处理的元素数量(吞吐量)也可能不同。Java 对象数组连续存放的是引用,对象本身未必连续,实际效果仍取决于数据布局。
9.3 数据分布
重复值总出现在数组前部时,提前返回会让平均耗时很低;全部唯一则会触发最坏路径。压测数据要接近生产分布。
9.4 JVM 运行状态
JVM 是执行 Java 程序的虚拟机。JIT(即时编译)会把热点代码编译为机器码;逃逸分析用于判断对象是否超出当前方法等范围,为分配优化提供依据;GC(垃圾回收)负责回收不再使用的对象。程序运行初期与稳定运行后的状态可能不同,因此基准测试需要预热。用 System.nanoTime() 只测一次调用,难以区分算法耗时、初始化成本与运行波动。
10. 正确做性能实验:复杂度分析加 JMH
JMH(Java Microbenchmark Harness)是 OpenJDK 提供的 Java 微基准测试框架,可帮助处理预热、重复测量和无效代码消除等问题。
下面是基准结构片段,并非独立可运行程序。实际运行需要 JMH 依赖、注解处理器及相关导入,还需提供片段引用的 DuplicateChecker.duplicateByHash()。输入由不同的数字字符串组成,用于覆盖无重复时的扫描路径。
java
@State(Scope.Thread)
/**
* 可运行示例:代码能跑不等于能用:时间复杂度如何决定系统上限。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class DuplicateBenchmark {
@Param({ "1000", "10000", "100000" })
int size;
String[] values;
@Setup
public void setup() {
values = IntStream.range(0, size)
.mapToObj(Integer::toString)
.toArray(String[]::new);
}
@Benchmark
public boolean hashSetSolution() {
return DuplicateChecker.duplicateByHash(values);
}
}实验时至少要明确:
- JDK 版本和 JVM 参数;
- 输入规模与数据分布;
- 预热和测量轮次;
- 吞吐量还是延迟模式;
- 内存分配与 GC 情况。
复杂度分析告诉我们增长方向,基准测试告诉我们具体实现的常数成本。两者不能互相替代。
11. 从业务规模反推可接受复杂度
先区分表中两种容易混淆的方法:回溯是逐步尝试选择、探索后续方案,再撤销选择并尝试其他分支的搜索方法,可以结合第 4.5 节的剪枝跳过无效候选。状态压缩则是用更紧凑的形式表示状态,例如用整数的二进制位记录哪些元素已选中,每一位的 1 或 0 分别表示选中或未选中。
状态压缩只改变状态表示,不自动减少指数级候选数量:n 个元素的全部子集仍有 2ⁿ 个。分析时仍需统计候选数量和每个候选的处理成本,不能把“表示更紧凑”理解成“搜索规模更小”。
下面只是帮助建立数量级直觉,不是硬性性能承诺:
| 输入规模 | 通常可以优先考虑 | 需要警惕 |
|---|---|---|
n <= 20 | 指数搜索、回溯、状态压缩 | 是否能剪枝 |
n <= 1,000 | 部分 O(n²) 算法 | 内层操作是否昂贵 |
n <= 100,000 | O(n log n)、O(n) | 对象分配和内存 |
n >= 1,000,000 | 接近线性或分块处理 | 内存、I/O 与并行开销 |
这些范围高度依赖时间限制、硬件和操作成本,不能直接作为生产 SLA(服务等级协议中约定的延迟、可用性等目标)。分块只能限制单批资源占用,也不自动降低总工作量。选型时应先明确接口允许的耗时和内存,再按以下步骤筛选:
- 获取真实输入上限;
- 估算核心操作数量;
- 排除数量级明显不可行的方案;
- 对候选方案做接近生产环境的测量。
12. 容易踩的坑
12.1 坑:嵌套循环一定是 O(n²)
循环次数可能是对数级,也可能两个指针总共只移动 n 次。应计算核心操作的总执行次数。
12.2 坑:HashMap 永远是 O(1)
Hash 查找通常讨论平均复杂度。Hash 质量、装载情况、冲突策略与恶意输入都会影响实际表现。
12.3 坑:只分析主循环,忽略内部 API
java
for (String value : values) {
list.contains(value);
}如果 values 长度为 n,list 是长度为 m 的 ArrayList,contains() 最坏需要扫描 m 个元素。按单次相等比较为常数成本计算,总体是 O(nm);当 m 与 n 同阶时,才可写成 O(n²)。
12.4 坑:递归看起来只有一行调用
斐波那契的朴素递归会重复计算大量子问题:
java
static long fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}每次调用又产生两个子调用,例如 fib(n - 2) 会在不同分支重复计算,调用数量呈指数增长。调用栈保存尚未返回的方法状态,递归深度随 n 线性增长,也需要额外空间。这里仅讨论非负 n 下的递归结构;long 范围有限,代码并不保证大输入的数值结果正确。
12.5 坑:优化了复杂度,却改变了业务语义
如果业务要输出有序的去重结果,直接遍历 HashSet 可能丢失原顺序;直接排序输入会改变调用方看到的数组顺序;近似结构可能产生误判。本文只返回“是否重复”,排序方案也先复制数组。优化前要明确业务不变量,即所有方案都必须保持的规则,包括输出含义、顺序和精确性。
13. 一套可复用的复杂度检查清单
提交涉及批量数据的代码前,可以依次检查:
n代表什么,线上最大值是多少?- 核心操作会执行多少次?
- 内部调用的集合或字符串 API 是什么复杂度?
- 最坏输入能否由用户或外部系统构造?
- 是否用额外内存换取时间,内存上限是否允许?
- 是否修改了输入顺序、稳定性或精确性?
- 性能结论来自复杂度推导还是可靠测量?
- 数据放大 10 倍、100 倍时,工作量如何变化?
14. 进阶:复杂度也是架构问题
单机算法不是唯一层次。100 万条数据如果必须从数据库全量读取到 JVM,即使内存算法是 O(n),整体仍可能受网络和 I/O 限制。
工程中经常需要同时考虑:
text
数据库过滤与索引
-> 网络传输量
-> JVM 内存结构
-> 单机算法复杂度
-> 并发与资源隔离本批次内没有重复,不等于共享存储中没有重复:两个请求可能各自通过内存检查,随后写入同一个订单号。此时需要数据库唯一约束,或能把“检查并写入”作为不可分割操作执行的存储接口,这就是这里所说的原子语义。内存检测可以提前给出友好错误,但不能替代共享数据层的一致性保证;约束键和作用范围仍须匹配业务规则。
算法思维的价值,正是把“能不能跑”推进到“在什么约束下可以稳定运行”。
15. 总结
时间复杂度不是一道数学附加题,而是输入规模增长时,代码能否继续工作的上限判断。
可带走的三个要点:
- 大 O 描述工作量的增长趋势,不等于实际秒数;性能结论还需要结合数据分布和可靠测量。
- 分析复杂度要计算核心操作总次数,并把集合、字符串和递归等隐藏成本算进去。
- 更低的时间复杂度往往需要额外空间或改变数据形态,算法选型必须同时满足业务语义与资源约束。
下一篇:先别急着写代码:如何把业务问题抽象成算法模型。完成建模后,再阅读算法正确性、测试与基准方法。