先还原一个很常见的下午。同事做订单的批量导入接口,本地一万条耗时 5 毫秒,他觉得没问题。上线后运营一次导了十万条,接口跑了 500 毫秒,前端还先超时了一次。他的第一反应是服务器忙、网络抖,或者数据库没走索引。
但用同样的数据、同样的机器再跑一遍,500 毫秒几乎不差。真正要盯住的不是这 500 毫秒,而是比例:数据量 10 倍,耗时 100 倍。如果只是变慢,时间该变成 50 毫秒左右。多出来的 10 倍,说明有工作在按数据的平方增长。
翻到代码,原因很简单:每读一行订单,都要在已读入的列表里再扫一遍查重。第一万行扫一万次,第二万行扫两万次,加起来是 1 加到 n,约等于 n 的平方除以二。数据量翻十倍,内层扫描的总次数翻一百倍。
这类判断不该等线上出事才做。读代码时把「操作次数随 n 怎么长」写出来,很多问题在压测前就能看见。这篇讲怎么数、为什么能粗略地数、循环的几种形状对应什么增长、递归怎么展开,以及最好、最坏、平均该看哪个。
现场:为什么不是慢了 10 倍,而是 100 倍
把问题缩成可跑的小函数:输入数组,去掉重复订单号。错误版本对每个元素都从头扫一遍,看前面有没有同样的值。
function dedupeSlow(arr) {
const out = [];
for (let i = 0; i < arr.length; i++) {
let seen = false;
for (let j = 0; j < i; j++) { // 每来一个元素,就回头扫一遍
if (arr[j] === arr[i]) { seen = true; break; }
}
if (!seen) out.push(arr[i]);
}
return out;
}
耗时不在创建数组和 push 上,而在内层循环。i 等于 1 时跑 1 次,i 等于 2 时跑 2 次,到 n 时跑 n 次,总次数是 n 乘 n 加 1 再除以 2。数据量从 1 万到 10 万,n 涨 10 倍,平方涨 100 倍,和 5 毫秒到 500 毫秒正好对上。
本机 Node.js 24 实测:n 为 500 时约 0.18 毫秒,1000 时 0.52 毫秒,2000 时 1.98 毫秒,4000 时 8.08 毫秒。每翻一倍,耗时约为上一次的 3.7 到 4.1 倍。这个「翻倍再翻倍」就是平方增长的样子。
这三层从具体到抽象。第一层最容易漏,因为只数最外层大循环,忘了里面还藏着一个;第二层最容易算错,因为边界常常不是简单的 n;第三层最容易引起误会,因为常数在工程上其实很重要。
基本操作怎么数:先给每条语句记 1
复杂度不是跑多少秒,而是工作量随 n 怎么变。先约定记账单位:一次赋值、比较、加法、按下标读取都算一次基本操作。约定很粗糙,但足够比较增长形状。
拿一个求和函数举例,循环体里有一次加法和一次下标读取,每轮还有一次比较和自增。
function sum(arr) {
let s = 0;
for (let i = 0; i < arr.length; i++) {
s += arr[i];
}
return s;
}
把次数加起来约是四次乘 n 再加两次固定开销,写作 T(n) 等于 4n 加 3。不需要数得和编译器一样准,因为下一步会化简成 n。要保证的是别漏掉一整个循环。
数的时候有个筛子:只有会重复的结构影响复杂度,也就是循环和递归。三条顺序语句和三百条顺序语句在复杂度上都是常数。很多人把初始化代码也数进去,得出吓人的式子,其实那部分可以整个忽略。
还要注意 n 指什么。数组长度、字符串长度、节点数都是常见的 n;矩阵的规模是行乘列,容易只数行不数列。图算法里 n 是顶点,边数记作 m,要分开,否则会把稀疏图当成稠密图。
为什么只保留最高阶,常数为什么可以丢
数出 T(n) 等于 3n 平方加 5n 加 7,化简是 O(n 平方):只留增长最快的一项,再丢掉系数。这不是偷懒,因为 n 足够大时低阶项占比趋近于零。
代数字就清楚了。n 等于 1000 时,3n 平方是三百万,5n 是五千;n 等于一百万时,3n 平方是三万亿,5n 只有五百万。决定「翻倍翻几倍」的只有最高阶那一项。
常数同理:O(2n) 和 O(n) 是同一种形状,n 翻倍时都翻倍,只是绝对值差两倍。但常数在工程上不能忽略。两个 O(n) 实现,一个每次做加法,一个每次分配内存,实测能差几十倍。复杂度只告诉你不会爆炸,不告诉你够不够快。
常见误会也在这里。两段各 n 次的循环算出 2n,觉得高一阶,其实还是 O(n)。给平方级代码加几个提前返回,耗时降一半,只是常数从 3 降到 1.5。真正降阶要改重复层数,比如把内层线性扫描换成哈希表。
单层、嵌套、两个独立循环:相加还是相乘
循环的复杂度只有两种组合:顺序执行相加,嵌套相乘。这是最容易出错的地方,也最实用。
单层循环跑 n 次是 O(n)。本机用 Float64Array 求和,n 为 10 万时每次约 0.080 毫秒,100 万时约 1.09 毫秒,1000 万时约 11.54 毫秒。后两步都是十倍左右;第一步偏小,是因为小数组刚好落在缓存里,每次访问更便宜。
嵌套两层也是 n 次,总次数 n 乘 n,O(n 平方)。内层写成 j 从 i 开始,次数是 n 乘 n 加 1 再除以 2,仍记 O(n 平方),因为二分之一是常数。前面的去重函数就是这种,实测每翻一倍约四倍。
两个循环先后执行、互不嵌套,总次数 2n,还是 O(n)。判断很机械:看第二个循环在不在第一个的循环体里面。在里面相乘,在外面相加,相加后只留最高阶。
三层嵌套是 O(n 三次方),比如枚举三个下标。小数据跑得动,n 到一千就可能要几秒。如果某层只跑固定十次,它相当于常数,不算进 n 的层数。
隐藏的坑:循环里调用的函数本身可能是线性的。遍历数组时对每个元素调用 includes 查另一个数组,外层只有一层,实际是 n 乘 m。数复杂度不能只看 for 的层数。
每次乘 2 或除 2,就得到对数
对数不需要复杂定义,一句大白话:log2 n 就是「把 n 反复除以 2,除几次能到 1」。n 等于 8 时除 3 次,1024 时除 10 次。它增长极慢,n 翻一倍,次数只多 1。
代码里出现对数,通常因为循环变量乘 2 或区间除 2。下面这个循环每次让 i 翻倍,次数就是 log2 n 向上取整。
function countSteps(n) {
let steps = 0;
for (let i = 1; i <= n; i *= 2) {
steps++;
}
return steps;
}
本机测了三组:n 一百万约 0.3 微秒,十亿约 0.4 微秒,一万亿约 0.6 微秒。n 涨了一百万倍,耗时只涨一倍,因为步数是 20、30、40。
更常见的是二分查找。每次砍一半,区间从 n 到 n 除 2 再到 1,最多比较 log2 n 加 1 次。二十万个查询实测:长度一万 16.81 毫秒,十万 24.23,一百万 35.16,一千万 89.54。n 涨一千倍,时间涨约 5.3 倍,多出的部分是缓存未命中。
乘起来就是 O(n log n)。归并排序每层合并 n 个元素,共 log n 层。n 到一百万时平方级基本跑不完,n log n 还能接受。
递归怎么展开:看每层分裂几份、树有多高
递归是函数调用自己。看到递归就默认慢并不准确。复杂度和循环一样能数:展开成一层层调用,看每层多少工作、一共多少层。
每次只递归一次、规模减一:T(n) 等于 T(n 减 1) 加 1,展开是 n 层,O(n)。阶乘、链表长度都属于这类。递归不改变复杂度,只是多了栈开销。
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1); // 每次只分出一个子问题,深度 n
}
每次分成两个规模减一的子问题,形状就变了。朴素 fib 调用 fib(n 减 1) 和 fib(n 减 2),次数约按 1.618 的 n 次方增长,粗记 O(2 的 n 次方)。n 到四十就明显卡顿。慢的原因是重复计算,不是递归本身。
更值得掌握的是每次把规模除以 2。归并排序 T(n) 等于 2 个 T(n 除 2) 再加 n:每层总工作量 n,树高 log2 n,总计 n log n。二分查找 T(n) 等于 T(n 除 2) 加 1:树只有一条枝,深度 log n,所以是 O(log n)。
快速幂同理。算 x 的 n 次方,每次把指数减半,先算一半再平方。
function pow(x, n) {
if (n === 0) return 1;
const half = pow(x, Math.floor(n / 2));
if (n % 2 === 0) return half * half;
return half * half * x;
}
递归深度 log2 n,每层常数次乘法,O(log n)。算二的十万次方,循环要乘十万次,快速幂约十七层。递归树的价值是把调用次数变成「每层工作乘层数」,比盯着代码猜可靠。
最好、最坏、平均:三个数不是一回事
同一段代码,输入不同,执行次数差很多。顺序查找最典型:目标在第一位,一次结束;在最后或不存在,比较 n 次。最好 O(1),最坏 O(n)。
平均要假设输入分布。目标等概率出现在每个位置时,平均比较 n 加 1 再除以 2 次,仍是 O(n)。如果九成查询命中前几条,真实平均值明显更低,这就是热数据的价值。
工程上更关心最坏,因为它决定延迟上限和容量规划。平均 10 毫秒、最坏 3 秒的接口,用户感受到的是那 3 秒。监控不能只看平均,要看 p99 甚至 p999。
插入排序能说明三者差别。已有序时内层不挪,共 n 次比较,O(n);完全逆序时每次挪到底,约 n 平方除二,O(n 平方);随机输入平均也是 O(n 平方)。
还要把平均和均摊分开。平均是对输入分布取期望,均摊是对一串操作的总成本做除法,给的是最坏序列下的保证。动态数组单次扩容 O(n),连续追加 n 次均摊 O(1)。下一篇整篇讲清。
O、Θ、Ω 三个符号到底在说什么
三个符号都在描述两个函数的增长关系,区别在「上界、下界、上下都卡住」。O 是最多这么慢,Ω 是至少这么慢,Θ 就是这么快。
O 给上界:n 足够大时,工作量不会超过某个函数的常数倍。说一个算法是 O(n 平方),意思是不会比平方更糟,也可能是线性的。Ω 给下界,Θ 是紧确界,既是 O 也是 Ω。
日常说法里的 O
工程交流里说「这个是 O(n log n)」,九成是在说 Θ(n log n),也就是就是这么快。这种宽松用法很常见,不算错,但要心里有数。
什么时候必须区分
解释「为什么最坏会超时」时必须区分。快速排序平均是 Θ(n log n),最坏是 O(n 平方)。只说 O(n log n) 就把最坏情况藏起来了。
另一个误用是把上界写大。任何 O(n) 都能合法说成 O(n 平方),因为线性不超过平方,但没有信息量。写法要尽量紧,写到再小一档就不成立为止。O(1) 表示常数时间,不表示很快。
空间复杂度记法一样,数的是额外内存随 n 怎么变。原地排序 O(1),归并排序 O(n),递归要算栈深度。很多人只数时间,忘了深度一万的递归在空间上也是 O(n)。
现象、原因与第一步排查
下面这些现象在真实项目里反复出现。看到类似症状,先按表里的第一步定位,不要一上来就换语言或者加机器。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 数据量 10 倍,耗时 100 倍 | 存在嵌套循环,内层边界也跟着 n 变 | 内层循环的上限是不是 i、n 或另一个数组的长度 |
| 代码只有一层 for,还是越来越慢 | 循环体里调用了线性函数,实际是 n 乘 m | 循环内是否调用了 includes、find、filter 这类遍历 |
| 加了缓存但命中率几乎为零 | 缓存 key 每次都不同,等于没缓存 | 打印命中率和 key 的构造方式 |
| 数据量涨 1000 倍,耗时只涨几倍 | 主循环是对数或常数形状 | 循环变量是不是乘 2,区间是不是每次折半 |
| 两个循环相加,被当成 O(n 平方) | 顺序执行是相加,不是相乘 | 两个循环是否嵌套,还是并排写 |
| 递归版本比循环版本慢一个数量级 | 同一子问题被重复计算,调用次数指数增长 | 递归树同一层是否出现重复参数 |
| 平均延迟正常,偶发超时 | 最坏情况被平均值掩盖 | 看 p99、p999 和最坏输入,不只看平均 |
| 换了个语言,同一算法慢三倍 | 常数差异,复杂度形状没变 | 先确认是不是常数问题,再决定要不要换实现 |
最容易误判的是第二行和第五行。第二行看起来只有一层循环,实际成本藏在函数调用里;第五行看起来循环更多所以更慢,其实并列的循环只是相加,最后仍然只留最高阶。判断的核心永远是:这段工作重复多少次,次数是不是随 n 一起长。
边界与代价:复杂度不管的事
复杂度是地图,不是导航。它忽略常数、缓存、内存分配、磁盘和网络。一个 O(n) 循环在内存里跑,另一个每条记录发一次远程请求,复杂度一样,耗时差几个数量级。
大 O 描述 n 很大时的趋势,n 很小时可能完全失效。哈希表查询 O(1),但存五个元素时往往不如直接遍历数组。理论上更优的结构在小规模下输给朴素做法,很常见。
测量也有边界。没预热的代码偏慢,只跑一次会被调度和垃圾回收干扰,结果被优化掉会测出假的小数。本文数字是本机 Node.js 24 多次取中位数,只说明量级和趋势。
最后是维护成本。为把 O(n 平方) 降到 O(n log n),把十行改成一百行,还引入排序和额外空间,不一定划算。先测量,确认瓶颈在形状上,再动手。复杂度用来排除灾难,不是用来炫耀。
当天能做的练习
- 把本文的
dedupeSlow敲进编辑器,n 取 500、1000、2000、4000,记录耗时,验证每翻一倍大约四倍,并算出 n 翻十倍时的理论倍数。 - 写三个函数:单层求和、两层嵌套、两个并列的单层循环,都处理 n 等于一万的数组。先写下预测的耗时关系,再实测,解释为什么第一个和第三个接近,第二个差出好几个数量级。
- 实现二分查找和线性查找,各查询十万个随机 key,数组长度分别取一万、十万、一百万。记录耗时,说明 n 扩大一百倍时各自涨了多少。
- 写朴素递归的
fib(30)和带记忆化的版本,打印调用次数和耗时,画出递归树,指出重复的子问题出现在哪几层。 - 找一段项目里的循环,标注它的最好、最坏和平均复杂度,说明哪种输入会走到最坏,监控里该看哪个分位数来发现它。
小结与下一篇
三句话收一下:复杂度数的是循环和递归的重复次数,不是秒数;系数和低阶项在 n 变大后可以忽略,但常数在工程上不能忽略;循环变量每次乘 2 或区间每次折半,就会得到对数形状。
下一篇讲均摊。这篇里已经碰到一个矛盾:动态数组扩容单次是 O(n),连续追加 n 次的平均成本却是 O(1)。这不是把最坏情况藏起来,而是一种可以证明的保证。下一篇从日志服务每隔一段时间抖一下的监控尖刺讲起,把聚合法、记账法、势能法逐个拆开。