刚入 OJ 那会儿我觉得最难扛的不是题目本身而是点击提交之后屏幕上弹出的 TLETime Limit Exceeded。代码明明能跑出正确答案偏偏就是慢那么零点几秒。后来我复盘才发现绝大多数超时都不是代码写得不熟练而是时间复杂度和空间复杂度没估算清楚甚至压根没估。这篇内容我就把复杂度这个概念从到底什么意思一直讲到如何在 OJ 上用它反推算法中间会穿插大量实际算例和踩坑记录希望能一次讲透。这篇文章适合三类人刚接触算法竞赛、正在刷 OJ 但频繁 TLE 的新手笔试面试前想系统整理复杂度知识点的求职者以及虽然会写代码但从来没认真算过自己程序要跑多久、要占多少内存的开发者。无论你刷的是华为 OJ、东华 OJ还是 LeetCode 这类在线评测平台复杂度的判断方法都是通用的。1. 复杂度到底是个什么东西为什么要盯住它不放1.1 从一段跑不完的代码说起想象一个最简单的问题给定一个长度为 n 的数组检测是否存在两个数之和等于 target。新手最容易写的版本就是双重循环外层枚举第一个数内层枚举第二个数总共比较 n*(n-1)/2 次写作 O(n²)。这里 n 很小比如 n100那最多才 4950 次比较瞬间就完成。但如果 n100000也就是常见的 OJ 数据规模O(n²) 意味着大约 5×10⁹ 次操作。按普通 OJ 一秒能跑 10⁸ 到 4×10⁸ 次简单运算来估算这段代码至少要跑十几秒妥妥超时。这就是复杂度的含义它不关心具体常数只关心随着输入规模 n 的增长运行时间或内存空间增长的趋势。1.2 大O记号的真实含义别被数学符号吓住大O记号看着唬人其实就是一个增长速度的上界。f(n)O(g(n)) 的意思是当 n 足够大时f(n) 的增长速度不会超过 g(n) 的某个常数倍。我们平时说的 O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)就是把常见增长量级从慢到快排了个序。关键点在于大O忽略常数因子和低阶项。比如 3n² 5n 100直接写成 O(n²)。因为当 n 很大的时候5n 和 100 跟 n² 相比完全是杯水车薪。我见过不少人纠结到底是 3n² 还是 n²其实在算法分析层面完全没必要真正影响决策的是量级本身。1.3 复杂度是趋势不是秒数这点我踩过坑用一小组测试数据跑了一下感觉秒出结果就以为 O(n²) 能过结果OJ 上的大数据一上来就崩。复杂度描述的是变化趋势而不是固定耗时。O(n) 和 O(n²) 在 n10 的时候几乎看不出区别但 n 每放大十倍O(n²) 的耗时就要放大一百倍。所以拿到任何题目第一反应不是能不能跑出正确结果而是n 的上限是多少我的算法在这个 n 下最快能到什么量级。下面几节我会给一套肉眼估算法让你在一分钟内就能判断出一段代码大概的复杂度和通过性。2. 时间复杂度怎么算、怎么判断、怎么犯错2.1 基本操作计数和循环嵌套分析时间复杂度的核心动作只有一个数基本操作被执行的次数。基本操作包括赋值、比较、算术运算、数组下标访问等通常认为它们各自耗时差不多。看代码块的时候我先看循环层数再看每层循环的规模。int sum 0; for (int i 0; i n; i) { for (int j 0; j n; j) { sum a[i][j]; } }外层跑 n 次内层每次跑 n 次总共 n² 次加法所以是 O(n²)。如果内层循环的条件是 j i那么执行次数是 n(n-1)/2同样是 O(n²)常数 1/2 被大O吞掉了。遇到 while 循环就去看每次循环变量怎么变化。比如二分查找每次区间缩小一半执行的次数是 log₂n 量级记为 O(log n)。2.2 递归的时间复杂度主定理和递归树的直觉递归的复杂度比循环稍微难算一点因为要看递归调用自身多少次以及每层递归做了多少工作。最典型的反面教材是斐波那契数列的朴素递归int fib(int n) { if (n 1) return n; return fib(n-1) fib(n-2); }每次调用会分出两个子问题子问题规模只减少 1 和 2递归树的高度是 n满二叉树节点数量级是 2ⁿ所以朴素递归是 O(2ⁿ)。这就是为什么 n40 以后会肉眼可见地卡顿。改成记忆化递归或递推每个状态只算一次复杂度就降为 O(n)。遇到递归先用递归树画一画每一层有多少个节点每个节点做多少事把这些乘起来就是总工作量。如果递归式子长得规整比如 T(n) 2T(n/2) O(n)可以套主定理结果是 O(n log n)归并排序就是这个模式。2.3 常见复杂度量级的故事化记忆我习惯把常见复杂度对应到具体场景这样判断起来特别快O(1)数组按下标取值、哈希表查找平均情况不随数据量变化。O(log n)二分查找、平衡树的查找数据量翻倍只多一次操作。O(n)遍历数组、求前缀和n 从 10⁵ 到 10⁶ 都很轻松。O(n log n)排序、线段树类操作n10⁵ 左右是常规上限。O(n²)双重循环遍历n5000 就得小心n10⁵ 基本不可能过。O(2ⁿ)枚举子集、朴素递归n 超过 25 就开始吃力。我给自己定的经验准则是C 在 1 秒内大约能执行 10⁸ 次简单操作Python 大约 10⁷ 次。假如 n10⁵能接受的复杂度上限大约是 O(n log n)n10⁶基本只能 O(n) 或 O(n log n) 里常数比较小的写法n10⁹就得思考数学公式或 O(log n) 级别的算法了。2.4 排序算法时间复杂度速查与选型提到复杂度排序是绕不开的应用场景而且 OJ 里大量题目直接依赖排序。先把表列出来排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定实际做题时如果题目只要求排序结果直接调用库函数就行C 的std::sort是快排和插入排序的混合Java 的Arrays.sort对对象用归并排序这些细节不需要自己实现。真正要会的是在特定场景下判断数据已经基本有序插入排序可能会跑出接近 O(n) 的表现需要稳定排序就得选归并要求原地且最坏情况不退化堆排序更稳妥。3. 空间复杂度很多人最容易忽略的那一部分3.1 空间复杂度的计算口径空间复杂度描述的是算法运行过程中额外占用的内存随输入规模增长的量级。注意两个词额外。通常我们只统计算法自己申请的额外存储比如辅助数组、哈希表、递归栈输入数组本身占的空间不计入。判断方法也很朴素看代码里开了多大的辅助数据结构。开了一个长度为 n 的数组空间就是 O(n)开了一个 n×n 的二维数组空间就是 O(n²)只用了几个变量空间就是 O(1)。有个常见的误区是忽略了输出。如果你要返回一个长度为 n 的答案数组那这部分空间算不算不同教程口径不同但在 OJ 场景下我一般把除了输入本身之外所有新建的内存都纳入考虑因为评测系统限制的是进程峰值内存输出结果所占用的内存也会被统计进去只是通常不太会成为瓶颈。3.2 递归栈空间隐藏的内存杀手这是我在做东华 OJ 时真正踩过的坑。递归函数每调用一次系统栈上就要保存一层现场包括局部变量、返回地址等。递归深度是 n栈空间就是 O(n)递归深度是 log n栈空间就是 O(log n)。比如归并排序很多人以为它的空间复杂度是 O(n)因为要合并数组。但其实如果用递归实现递归深度 log n 层的栈空间也要算进去总的空间复杂度是 O(n log n) O(n)因为 n 主导。反过来如果一个递归算法的深度是 n比如单链表反转的递归写法栈空间就是 O(n)如果 n 到 10⁶程序可能直接栈溢出这种情况就要改成迭代写法。3.3 原地算法和常见空间优化套路所谓原地算法就是只使用 O(1) 额外空间完成操作。典型的例子是数组原地反转、原地去重以及经典的两个变量交换数值。提到这个正好说说热词里那个很有意思的问题C 中异或的时间复杂度。异或运算本身是位运算单次执行 O(1)不存在某种运算的复杂度这种说法。真正的问题是用异或实现的算法整体复杂度是多少比如用异或交换两个整数a ^ b; b ^ a; a ^ b;三个异或操作每次 O(1)所以整个交换是 O(1) 时间、O(1) 空间非常漂亮。再比如找数组中唯一出现一次的数字其他数字都出现两次用 0 依次异或所有元素一次遍历 O(n) 时间只用一个变量 O(1) 空间不需要开哈希表。这就是位运算在复杂度上的优势。空间优化的常见思路是滚动数组。比如背包问题用二维 DP 时状态转移只用上一行的数据就可以把二维数组压缩成一维空间从 O(n²) 降到 O(n)。代价是代码逻辑需要调整遍历方向但这在 OJ 上非常实用因为很多题目的内存限制卡得比较紧。4. OJ 实战从看题到 AC 的完整思考路径4.1 拿到题先估算数据范围很多同学打开 OJ 题目直接写代码我觉得这是 TLE 的根源。正确顺序应该是先看约束条件里的数据范围再决定能接受的时间复杂度上限最后才是写码。比如华为 OJ 的某些题n 最大 10⁵时限 1 秒那你的算法必须在 O(n log n) 以内最好常数还小。如果看到 n 最大 10³那么 O(n²) 完全没问题甚至 O(n³) 都可能过。先把复杂度目标定下来后面所有设计都围绕这个目标展开比写完再优化效率高得多。我给自己定了一个速查表基本覆盖常见 OJ 场景数据规模目标复杂度典型算法示例n ≤ 10O(n!) / O(2ⁿ)暴力枚举、状态压缩n ≤ 20O(2ⁿ) / O(n·2ⁿ)状态压缩 DPn ≤ 500O(n³)Floyd、区间 DPn ≤ 5000O(n²)双重循环 DPn ≤ 10⁵O(n log n)排序、二分、线段树n ≤ 10⁶O(n)线性扫描、哈希n ≤ 10⁹O(log n) / O(√n)二分答案、数论公式4.2 目标复杂度反推算法确定目标复杂度之后反推算法就变成了一件特别顺的事。假设题目要求两数之和等于 targetn 到 10⁵。O(n²) 的双重循环不能过所以要把内层查找从 O(n) 优化成 O(1)。哈希表查找是 O(1)于是用哈希表记录已经见过的数和它的下标一次遍历判断 target - current 是否在表里整体 O(n)。再比如求逆序对数量暴力是 O(n²)。看到 n10⁵ 就明白必须换思路用归并排序在合并过程中统计逆序对复杂度 O(n log n)。目标复杂度一确定要用什么算法基本就是套模板的事。4.3 一道经典题的复杂度推导实战我用最大子数组和来完整走一遍推导过程。最暴力的做法是枚举所有起点 i 和终点 j再求和三重循环 O(n³)。稍微优化一下固定起点 i终点 j 从 i 到 n 依次累加O(n²)。但如果 n10⁵O(n²) 就完蛋了。Kadane 算法的思路是遍历数组维护以当前位置结尾的最大子数组和要么从前一个位置的延续要么从当前位置重新开始。整个算法只有一个循环O(n) 时间O(1) 空间。这就是从 O(n³) 一路优化到 O(n) 的过程每一步都靠复杂度分析驱动决策。我在 OJ 上做这类题目的感受是一旦你养成了先定复杂度目标的习惯代码写起来反而更快因为你不会在错误的暴力方案上浪费调试时间。4.4 C 中的隐藏复杂度陷阱热词里提到C 中异或的时间复杂度其实还牵扯出一个更常见的坑C 里有些操作不是表面看上去的 O(1)如果不注意时间复杂度的估算会失真。比如字符串的操作在一些旧实现里可能涉及重新分配内存和拷贝最坏情况下单次是 O(len)连续 n 次就可能是 O(n²)。再比如把std::map当成 O(1) 容器来用实际上它是红黑树单次操作 O(log n)n 次操作 O(n log n)。还有嵌套循环里用vector.size()不是问题但在循环内频繁插入删除 vector 可能会触发扩容和元素搬移。这类陷阱的判断方法很简单遇到容器操作先问一句这个操作底层是数组还是链表还是树有没有隐藏拷贝。数组按索引访问 O(1)但插入删除可能 O(n)链表插入删除 O(1)但查找 O(n)树结构查找 O(log n)。复杂度分析如果想准确不能只数循环还要把容器操作的代价算进去。5. 常见问题与排查技巧实录5.1 一个坑常数项没算进去大O符号丢弃常数但在 OJ 上常数可能会决定生死。比如同样是 O(n²)内层循环体是一个简单的加法和每次调用一个map的find内部还有 log 操作实际耗时是完全不同的。我遇到过 n2000 的 O(n²) 算法因为内层用了高常数操作而超时。所以我的经验是先用大O确定量级再用1 秒约 10⁸ 次简单操作作为常数参考。如果 n10⁵O(n log n) 大约 1.7×10⁶ 次非常安全O(n²) 是 10¹⁰ 次无论常数多低都过不了。量级差太远就不纠结常数量级接近时才需要优化常数。5.2 一个坑把最坏情况当成唯一标准算法分析里最坏情况、平均情况、最好情况是三种口径。OJ 评测数据通常包含多种测试有些是随机数据有些专门卡最坏情况。比如快排平均 O(n log n)但已经有序的数组能让普通快排退化成 O(n²)。这就是为什么实际写代码要用std::sort因为它针对退化情况做了优化。做题的时候我建议同时考虑最坏输入会不会卡死和平均输入有没有更好的选择。有的题目最坏情况 n 很大但随机数据下 O(n log n) 算法跑得很快那就要看 OJ 会不会放专门构造的数据。稳妥永远是先保证最坏情况能过再考虑平均优化。5.3 一个坑递归爆栈空间复杂度的隐藏坑最常见的就是递归深度。在一些 OJ 上默认栈空间有限递归深度到 10⁵ 就可能栈溢出而 n10⁵ 的递归深度在树形结构题目里很常见。解决思路有两个一是把递归改成显式栈的迭代写法空间复杂度不变但内存分配在堆上上限更高二是先用空间复杂度估算栈开销如果 O(n) 的递归栈可能超限尽早换方案。这个问题在 C 里尤其明显很多 OJ 的默认栈大小是 1MB 到 8MB别等爆栈了才回头看代码。5.4 超时排查速查表我把自己调试超时问题的固定流程整理成了一张表每次 TLE 都按这个顺序查排查项检查方法常见结论算法量级计算 n 和循环层数估算总操作次数O(n²) 超过 10⁹ 基本要换算法隐藏常数检查容器操作、字符串拼接、输入输出方式高常数操作拖垮性能输入输出检查是否用了未关闭同步的 cin/cout大量输入时建议用 scanf/printf 或 ios::sync_with_stdio(false)递归深度观察是否有深递归导致栈溢出改成迭代或显式栈数据范围检查数组越界或溢出导致死循环边界条件异常会卡住6. 把复杂度思维内化成肌肉记忆分析复杂度这件事熟练之后其实是不需要刻意想的。我做题的第一步永远是看数据范围这一步花 10 秒却决定了整道题的难度走向。时间复杂度和空间复杂度不只是考试知识点它们是我在 OJ 上判断要不要继续这个思路的硬指标。后来我面国内大厂时面试官问的很多算法题本质上也是在考同一件事你能否在给定数据规模下选择一个复杂度正确的解法。如果你正在刷题我建议你每次提交之前先在草稿纸上写下三行n 的范围是多少我的算法是 O(几)换算成 1 秒能不能跑完。这个习惯坚持两个月你对复杂度的直觉会变得非常准看到题目基本就能判断出出题人的意图。TLE 虽然让人烦躁但它恰恰是逼着你建立复杂度意识的最快途径。