★ FEATURED ARTICLE 朋友找我调一个线上接口变慢的问题日志里看不出异常数据库也说不慢。我顺着调用链翻到一段代码才发现问题出在两层for循环里嵌套了一次外部 HTTP 请求——列表几千条、两两组合几百万次网络调用不慢才怪。这种问题其实根本不用等线上告警写代码的时候用算法的时间复杂度和空间复杂度粗算一笔账就能提前预判。这也是我想写这篇文章的原因复杂度分析不是什么高高在上的理论而是每个写代码的人都该有的一种“估命”能力。下面我按自己多年的使用经验把这两个概念拆开讲透。文章不打算讲成一章教科书而是围绕“它到底在度量什么、怎么算、哪里最容易翻车、实际工作中怎么用”来展开内容同时适合准备算法面试、刷 LeetCode 和蓝桥杯这类竞赛题的人也适合工作多年但一直靠直觉写代码、想补一补底层功底的工程师。1. 我为什么在工作多年后重新啃这块硬骨头1.1 复杂度分析不是学术概念而是一把“预判尺”很多人对时间复杂度、空间复杂度有误解觉得这是大学《数据结构与算法》课程里的作业题考试考完就扔了。但工作越久我越发现真正区分“能写代码的人”和“会设计代码的人”的就是有没有在动手之前用复杂度算一笔账的能力。回到开头那个线上接口的例子。那段代码的问题不是内存溢出也不是数据库慢而是循环套循环再加上网络 I/O。如果写代码的人当时做一次粗略的估算外层列表长度n内层列表长度m每次执行还要发起一次 HTTP 请求总耗时大约是n * m * 单次请求延迟。当n 5000、m 50的时候这就是 25 万次网络请求哪怕每次只要 50 毫秒总耗时也超过 3 小时这接口不慢才怪。复杂度分析的价值就在这个地方——它是在程序还没有运行之前用几个变量关系就能预言程序在大数据量下会怎么表现。性能测试和 profiling 工具都是“事后诸葛亮”复杂度分析才是“事前诸葛亮”。你可以不懂复杂的数学证明但至少要会用复杂度估算这个工具在方案评审、需求评估、代码 review 的时候提前把风险拦下来。1.2 面试和竞赛里复杂度几乎是个“入场券”这几年我陆续帮朋友做算法面试模拟也看过不少 LeetCode、蓝桥杯、Codeforces 的题解发现一个共通点复杂度的优先级永远排在第一位。拿到一道算法题第一件事不是想“用哪个 API”而是看数据规模能允许什么复杂度。数据规模是n 20你可以放心用指数级搜索数据规模是n 10^5你就要老老实实奔着O(n)或O(n log n)去设计。面试官问“你能说一下这个方案的复杂度吗”本质上就是在确认两件事第一你有没有真正理解你的算法结构第二你有没有能力在大数据量下预判方案可行性。这个问题答不上来哪怕代码跑对了面试评价也会明显降一档。不仅仅是刷题。你写排序、写字符串匹配、写树和图的遍历甚至调深度学习模型的训练循环都需要用同一套尺子去评估候选方案的可行性。可以说理解了复杂度你才算真正开始“设计”算法而不是“背”算法。2. 大O记号是一把尺子但有它自己的刻度2.1 大O在度量什么函数的增长趋势不是真实耗时很多人第一次接触大O记号的时候容易把它理解成“程序跑了多少毫秒”。这是最大的一个误区。时间复杂度里的O(n)、O(n^2)衡量的不是一个具体的时间而是基本操作次数随输入规模 n 的增长趋势。在分析时我们假设代码里每个简单操作用时大约相同统计整个算法执行了多少次操作记为T(n)。然后忽略常数系数、低阶项只留下增长最快的那一项就得到了大O表示。比如某段代码的操作次数是3n^2 5n 10当 n 很大的时候5n 10和3n^2相比几乎可以忽略系数 3 也不影响增长速度所以时间复杂度写作O(n^2)。有个很贴近生活的类比如果我们要在 N 本书里找一本指定的书一本一本地翻是线性时间要是按拼音排好序之后再二分查找那就是对数级别的时间。两者在 10 本书时感觉不出差别但在 100 万本书时差别是“几秒”和“几次查找”的距离。2.2 常见的七档复杂度量级在实际分析算法时经常遇到的基本是下面这几档。把它们的位置和典型场景记住绝大多数复杂度分析都能对号入座。复杂度量级名称典型场景O(1)常数时间数组按下标访问、哈希表查询O(log n)对数时间二分查找、平衡二叉搜索树查找O(n)线性时间单次遍历数组、链表O(n log n)线性对数时间归并排序、堆排序、快排平均情况O(n^2)平方时间双层循环、冒泡排序、插入排序O(2^n)指数时间枚举全部子集、无优化回溯搜索O(n!)阶乘时间枚举全排列、旅行商暴力解重点说两个容易懵的边界。log n在算法分析里一般以 2 为底但底数对渐进复杂度没有影响所以统一写成log n。另外指数增长比平方增长可怕得多——n 30的时候n^2是 9002^30已经超过 10 亿。这就是为什么很多题只要 n 稍微大一点暴力搜索就会被立刻判死刑。2.3 Θ、Ω 和大O的区别以及为什么工程里只说大O严格来说大O记号、Ω记号和Θ记号分别表示的是上界、下界和“上下同阶”。f(n) O(g(n))表示f(n)的增长不会超过g(n)的某个常数倍也就是“最多这么慢”Ω表示“至少这么快”Θ表示两者增长速度相同。但在真实的工程讨论和面试里大家几乎只使用大O。原因很简单我们做容量规划、预判性能风险的时候最关心的是最坏不会超过多少即上界。比如一个哈希表平均查询是 O(1)最坏可能退化到 O(n)如果你只知道平均复杂度而不知道上界线上遇到恶意构造的冲突输入就可能被打挂。用大O记号描述“最坏运行时间的上界”是最保守、最不容易翻车的说法。这也引出一个说法习惯问题当你说“这个算法时间复杂度是 O(n log n)”时最好在心里明确自己说的是哪个口径——是最坏情况、平均情况还是最好情况这恰恰是很多文章和面试答案模糊不清的地方我后面会专门展开。3. 几个反直觉的复杂度案例从暴力枚举、剪枝到KMP3.1 暴力枚举的复杂度为什么常常被低估暴力枚举是很多人入门时最先写的解法但它的复杂度也最容易被低估。比如经典的“两数之和”问题最直接的解法是两层 for 循环对每个(i, j)组合相加时间复杂度是 O(n^2)用哈希表把每个数存下来查找补数时就是 O(1)整体降到 O(n)。关键在于嵌套层数不等于复杂度层级。我曾见过有人把三层循环写成 O(n^2)因为内层循环总是在一个小的固定范围内跑——确实如果第三层循环的次数是常数 k那整体就是 O(n^2 * k)系数 k 被忽略后还是 O(n^2)。但也有很多情况内层循环的次数取决于外层变量i比如j从i1到n总次数是n(n-1)/2仍然是 O(n^2)。所以分析的时候要老老实实把所有循环次数乘起来不要凭直觉拍脑袋。还有一个高频低估场景是子集枚举。一个n个元素的集合有2^n个子集写位运算枚举的时候看起来只是一个循环实际上因为每一个二进制位都在涨整体复杂度是 O(2^n)。同样的思路全排列就是 O(n!)。这类暴力算法在n 20左右还能勉强跑到n 30以上基本必死无疑这也是竞赛题里“数据范围一上来就看 n 有多大”的原因。3.2 剪枝没有改变最坏上界但改变了可解规模很多人对剪枝算法有一个错觉既然加了剪枝复杂度一定降下来了。严格说不是这样。以 N 皇后问题为例纯暴力回溯搜索的复杂度是最坏 O(N!)加上了“列、对角线冲突”的剪枝后实际能搜到的分支少了很多N 20 左右在工程上也能跑出结果。但最坏情况下比如某些构造数据搜索空间依然可能退回到接近 O(N!) 级别。所以我的理解是剪枝优化的是“实践中的运行时间”它让许多本来会指数爆炸的搜索在真实输入上变得可接受但并没有在渐进意义上改变最坏上界。做复杂度分析的时候你可以在平均情况里提“由于剪枝实际运行远好于最坏上界”但不要把剪枝后的算法写成 O(n^2) 这种等级否则别人按最坏数据构造测试时你一定会被打脸。这个思路同样适用于搜索算法里常见的“如果当前成本已经超过已知最优解就直接返回”这类分支限界手段。这类技巧在工程里非常有用但要诚实地把它们记为“工程优化”而不是“复杂度降低”。真正能把指数级拉成多项式级的只能是更本质的算法设计比如动态规划、记忆化搜索、双指针、哈希预处理。3.3 KMP为什么能到 O(n m)前缀函数让模式串不回退字符串匹配是另一个复杂度教科书案例也是面试高频题。最简单的朴素匹配算法是文本串从每个位置开始和模式串逐位比对一旦失配就回到文本串下一位重新开始。最坏情况下比如文本串是AAAAAAAAAAAAAA、模式串是AAAB每次都只能比到最后一位才发现不匹配复杂度是 O(n * m)。KMP 算法的核心改进在于用**前缀函数next 数组**提前记录模式串自身的前缀信息让匹配失败时文本串的指针i不回溯只有模式串的指针j根据 next 数组回退。按照这个逻辑文本串每个字符最多只会被比对一次所以匹配过程是 O(n)加上构建 next 数组的 O(m)总复杂度就是 O(n m)。下面用一个简化的 KMP 匹配骨架说明这个思想def kmp_search(text, pattern): nxt build_next(pattern) # O(m) i j 0 while i len(text): # 文本指针 i 不回头 if text[i] pattern[j]: i 1 j 1 if j len(pattern): return i - j elif j 0: j nxt[j - 1] # 模式串指针按前缀函数回退 else: i 1 return -1亲眼看到这个结构之后你就能理解为什么 KMP 是线性的文本串指针i从头到尾不会回退总移动次数不超过n模式串指针j每一步要么前进要么根据 next 回退而回退的总次数也不会超过前进的总次数m。这就是它复杂度推导最直观的地方也是面试时展现你“理解原理”而不是“背模板”的关键。3.4 递归复杂度的三种典型形态以及主定理递归的复杂度分析比循环更难因为需要展开成递推式。我先说三种最常见的形态。第一种是线性递归比如T(n) T(n-1) O(1)每层只往下递归一层总深度是 n所以复杂度是 O(n)。第二种是分治递归比如归并排序T(n) 2T(n/2) O(n)每一层做的事情总耗时是 O(n)层数是 log n合起来是 O(n log n)。第三种是没有记忆化的递归比如斐波那契数列def fib(n): if n 1: return n return fib(n - 1) fib(n - 2) # T(n) T(n-1) T(n-2) O(1)把这个递归树画出来会发现它是一棵近似满的二叉树节点数指数增长所以复杂度是 O(2^n)。这也是为什么面试官看到你不加记忆化写斐波那契会立刻追问“这个复杂度是多少能不能优化”。加上一个缓存数组就变成记忆化搜索状态数从指数级变成 n复杂度直接降成 O(n)。碰到更复杂的分治递推可以用主定理快速判断对于T(n) aT(n/b) O(n^d)比较a和b^d的大小前者大则复杂度是 O(n^(log_b a))两者相等则 O(n^d log n)后者大则 O(n^d)。实际工作中我很少逐项证明主要靠主定理这个结论快速推断大部分分治算法都套得进去。4. 空间复杂度不只会算数组递归栈才是最容易踩的坑4.1 空间费用的“记账规则”额外空间才是重点空间复杂度分析相对时间复杂度来说总被轻视但考察频率一点都不低。首先要明确记账规则空间复杂度一般只统计算法额外申请的内存不把输入数据本身占用的空间计入。比如你写一个函数传入一个长度为 n 的数组函数内部不开新数组只用了几个临时变量那就叫原地算法空间复杂度 O(1)。几个常见的空间开销来源要能一眼识别。新建一个哈希表存中间结果就是 O(n)归并排序需要临时数组合并左右两半额外空间 O(n)快排虽然不用额外数组合并但递归调用会占递归栈平均 O(log n)堆排序是在原数组上反复调整堆额外空间 O(1)。如果面试时被问“这个算法能不能原地做”本质上就是在问“你能不能让额外空间从 O(n) 降到 O(1)”。我还见过不少人犯的一个错误函数里拷贝了一份输入的切片或者子串来“方便处理”然后淡定地说空间 O(1)。这在理论上已经变成 O(n) 了尤其在大数据处理场景里这种隐式拷贝带来的内存和拷贝开销往往是真实性能瓶颈不只是面试里的一个扣分点。4.2 递归栈空间深度决定程序会不会崩空间复杂度分析最容易翻车的地方是递归函数。每一次递归调用系统都要在调用栈上压一帧这一帧里保存局部变量、返回地址等信息递归深度是多少栈空间就是多少所以递归算法的空间复杂度等于递归深度。比如二叉树递归遍历。平衡二叉树的高度是 O(log n)递归栈空间就是 O(log n)。但如果是极端链条状二叉树高度等于节点数 n递归深度就是 n空间复杂度变成 O(n)。这里有个真实踩坑经历我帮人排查过一个递归填满二维网格的程序逻辑本身没问题但网格边长一放大递归深度直接冲上几万层程序先是变慢然后直接栈溢出崩溃。解决办法要么改成显式栈迭代要么用 BFS 队列。关于尾递归多说一句某些语言比如很多函数式语言会优化尾递归让递归空间变成 O(1)但 Python、Java 这类主流语言默认不优化写深递归一样爆栈。所以分析空间复杂度时不要想当然地认为“既然是尾递归就肯定不占栈”先确认你用的语言和运行时到底做不做这个优化。4.3 空间换时间的经典套路从斐波那契到缓存系统空间和时间往往是跷跷板最经典的教学案例就是斐波那契数列。暴力的无记忆化递归是 O(2^n) 时间、O(n) 栈空间加一个 dp 数组做动态规划时间降到 O(n)空间升到 O(n)再用滚动数组只保留前两个值时间还是 O(n)空间降到 O(1)。这个“空间换时间”的思路在实际工程里无处不在。哈希索引是为了把查找从 O(n) 降到 O(1) 而多占内存缓存系统是用热点数据的空间换取重复计算时间的大幅下降布隆过滤器用极少的比特位快速判断“一个元素一定不在集合里”本质也是在用空间换取查询时间上的巨大收益。我自己做优化的时候有个原则先看时间瓶颈是不是真的存在再看空间是否有余量最后才决定要不要用空间换时间。盲目压缩空间而把时间复杂度堆上去才是最常见的得不偿失。反过来如果内存本来就不是瓶颈那花 O(n) 空间换 O(n log n) 到 O(n) 的时间就是非常划算的买卖。5. 复杂度分析的三重边界常数项、最好/最坏/平均、理论与实践5.1 忽略常数不代表常数不存在大O记号会丢掉常数系数和低阶项这是它方便的地方但也导致一个容易被误解的结论O(n^2) 一定比 O(n) 慢答案是不一定。当 n 很小的时候一个常数项很大的 O(n) 算法可能比一个实现得非常轻快的 O(n^2) 算法慢得多。举一个真实发生过的例子。快速排序的平均复杂度是 O(n log n)插入排序是 O(n^2)看起来快排稳赢。但实际工程里当待排序数组长度只有几十的时候插入排序的常数极小、内存访问又连续反而往往更快。所以 Python 内置排序用的 TimSort 会在数组过短时切换到插入排序这就是在“渐进复杂度和真实常数开销”之间做平衡。你可以把大O理解为“大数定律”它描述的是规模趋近很大时的趋势不是小规模下的具体胜负。5.2 最好、最坏、平均先定口径再审结论复杂度最容易被含糊带过的另一个点是没有说清分析的是哪种情况。同一个算法最好、最坏、平均复杂度可能完全不同。快排就是最典型的一个最好和平均是 O(n log n)但已经有序的数组上如果选固定第一个元素做基准就可能退化成 O(n^2)。所以工业实现会用随机选基准、三数取中等手段让最坏情况很难被触发。面试时如果只说一句“快排是 O(n log n)”而不限定为平均情况严格来说是信息不足的。哈希表同理。理想情况下查询是 O(1)但如果哈希函数设计不当大量元素碰撞进同一个桶查询就会退化到 O(n)。这也是为什么设计哈希表时不仅要关注平均情况还要考虑最坏情况下的抗碰撞能力。还有一个容易被忽略的概念是摊还复杂度。比如动态数组扩容单次 push 在最坏情况下需要把所有老元素复制到新数组单次是 O(n)。但数组容量是倍增的平摊到每一次 push 上平均成本只是 O(1)。分析这种带周期性重操作的数据结构时要说明自己用的是均摊口径不要拿单次最坏去吓人。5.3 理论复杂度不等于实际性能两个反直觉的工程实例我在实际优化中碰到过不少“理论更优但实际更慢”的情况。第一个典型是缓存局部性。数组顺序遍历时 CPU 会预取相邻内存到高速缓存速度很快而链表遍历因为节点散落在内存各处缓存命中率低即使理论上同样是 O(n)链表遍历的实际耗时可能差好几倍。第二个典型是常数项巨大的 O(n log n) 算法可能被一个常数项极小的 O(n) 算法按在地上摩擦。所以正确的工程姿势是先用大O分析把明显不合理的方案过滤掉再对留下来的候选方案做 profiling用真实数据验证。复杂度是决策的第一层过滤器而不是最终裁判。我自己的习惯是写代码前先算复杂度确保方案量级正确代码跑通后再用 profiling 确认热点最后才做常数级别的优化比如减少内存分配、优化循环顺序、合并多次遍历。6. 面试与刷题场景下如何把复杂度分析变成肌肉记忆6.1 从数据规模反推目标复杂度一张经验表我自己刷题和带人刷题时会先教一个经验法则拿到题先看数据规模反推你需要的复杂度。这比任何高级算法知识都更先落地。下面这张表是我多年比赛和面试总结出的粗粒度对应关系不是严格定理但非常实用数据规模 n可接受的复杂度范围常见策略n ≤ 10O(n!) 或 O(2^n * n)暴力枚举全排列、子集n ≤ 20 25O(2^n)状态压缩、子集枚举n ≤ 100 500O(n^3)区间 DP、Floyd 类算法n ≤ 1000 5000O(n^2)朴素 DP、双层循环n ≤ 10^5O(n log n) 或 O(n)排序、哈希、双指针、线段树n ≥ 10^6O(n) 或 O(log n)线性扫描、二分、常数较优的线性n ≥ 10^7 10^8O(n) 且常数要小尽量单次遍历避免高开销操作举例来说看到n 10^5你就要知道 O(n^2) 大概率超时O(n log n) 是安全线。反过来看到n 20你就不该去设计一个复杂的 O(n log n) 算法强行找罪受直接暴力搜索反而又快又不容易写错。这个“先看规模再定复杂度然后选算法”的顺序是我最想传达的肌肉记忆。6.2 面试作答三步法方案先行、复杂度报告、优化答辩面试和算法交流时描述一个方案最好固定成一个三步结构既显专业也方便对方理解。第一步先说明思路和用到的数据结构第二步明确报出时间复杂度和空间复杂度最好补一句推导依据第三步被追问的时候按“能不能降低一个量级、能不能原地优化、能不能预处理”的顺序想优化。举个例子求两个有序数组的交集。朴素写法是两层循环O(n * m)看到有序这个条件可以想到归并双指针时间 O(n m)额外空间 O(1)如果还允许使用哈希表预处理可以做到平均 O(n m) 时间加 O(min(n, m)) 空间。现场把这三个方案和对应的复杂度都摆出来面试官就很难再挑出毛病。我模拟面试的时候常跟人说报复杂度不是在背书而是在展示你对算法操作次数的掌控感。6.3 我的日常分析检查清单以及一点收尾经验最后分享一份我在实际写代码和 review 代码时用的复杂度检查清单写代码前先看数据规模反推目标复杂度不要拿到题就开写。找代码里的嵌套循环把每一层的迭代次数乘起来确认内层是否依赖外层变量。看到递归和回溯先画递归树估算层数和分支数没加记忆化的斐波那契式递归直接警惕指数爆炸。计算空间复杂度时别只数数组和哈希表递归栈深度也要算进去。报复杂度时说明口径最坏、平均还是均摊说时间复杂度不要忘记空间复杂度。我个人在指导别人和实际写代码时最深的体会是复杂度分析不是为了在面试时背出那几个符号而是为了让你在写代码的当下就能对程序在大规模数据下的命运有数。这种“有数”的感觉才是算法功底真正转化为工程能力的地方。希望这篇文章能帮你也建立起这种预判直觉。
阅读完成 · 觉得有帮助？
