最近带学弟学妹备赛的时候，发现一个特别普遍的现象：板子背得滚瓜烂熟，线段树、KMP张口就来，可是一提交就是一片红，不是TLE（Time Limit Exceeded）就是MLE（Memory Limit Exceeded）。问他们为什么卡了，十有八九答不上来——不知道自己的算法是几阶复杂度，不知道这题的时间限制和内存限制到底意味着什么，更不知道复杂度分析这回事在竞赛里是用来干嘛的。
这篇文章就专注讲透一件事：时间复杂度和空间复杂度在ACM/OI里到底是怎么用的，怎么靠它在一开始就判断思路能不能过，怎么在TLE和MLE之后快速定位问题。我会把估算方法、常见坑、还有我自己频繁踩过的教训都揉在一起写，尽量让看到这篇文章的人能直接在比赛中用上。
1. 复杂度的本质：它不是学术概念，是比赛成绩的晴雨表
1.1 大O记号到底在描述什么
很多人对时间复杂度的印象停留在“算法导论第一课”，觉得它是理论课上的东西，跟实际写题关系不大。这是最大的误区。
大O记号描述的是：当输入规模n趋向无穷大时，算法运行时间随n增长而增长的趋势，忽略常数因子和低阶项。比如某个算法实际执行了3n^2 + 5n + 100条指令，它的复杂度就是O(n^2)。这里的3、5、100都是常数，在n很大的时候完全不影响增长趋势。
但竞赛里更实用的理解是：大O记号的真正作用是画出一条“能不能过”的及格线。对一个具体的n，你可以用复杂度阶数反推算法大约要执行多少次基本操作，然后跟评测机的性能上限对比，提前判断会不会TLE。同理，空间复杂度就是反推代码要占多少内存，跟内存限制对比，提前判断会不会MLE。
1.2 为什么同样的代码换台评测机就可能TLE
很多人在本地机器上一跑，0.2秒出结果，交上去却TLE，然后怀疑评测机垃圾。这不是评测机的锅，而是本地测试数据规模不够。
假设评测机每秒稳定执行10^9条加法指令（这是一台普通O2优化下C++程序的量级，我们后面细说），你的本地测试n=10^4，O(n^2)的代码跑完大约0.1秒，体感“很快”。但评测数据里n=10^6，那么执行次数是10^12，需要10^3秒——超过16分钟。评测程序早就超时了，而你在本地测不出来。
这就是时间复杂度的实际意义：它让你在写代码之前、在本地小数据测试之后，都能用纸笔估算出这个算法在大数据下的表现，而不是靠玄学“觉得能过”。
空间复杂度同理。本地内存16GB，随便开数组都不爆，但竞赛题目内存限制经常是64MB、128MB、256MB。一个int a[10000][10000]就要400MB，本地一点问题没有，交上去直接MLE。不看空间复杂度，出了问题只能干瞪眼。
2. 常见复杂度量级对照表：对着数据范围选算法
2.1 一张表解决八成选型问题
竞赛题一般会给出每个数据点的规模，比如“n≤10^4”“n≤10^5”“n≤10^6”。看到这些范围，第一反应就应该是复杂度量级天花板。下面这张表是我平时做题时的条件反射，背下来基本能覆盖大多数题：
| n的数据范围 | 能接受的复杂度上限 | 典型算法 |
|---|---|---|
| n≤10 | O(n!) | 全排列、暴力搜索 |
| n≤20~22 | O(2^n) | 状态压缩枚举、子集DP |
| n≤30~50 | O(n^4)或O(2^(n/2)) | 折半搜索、Floyd变体 |
| n≤100 | O(n^3) | Floyd、三重循环、矩阵乘法 |
| n≤500~1000 | O(n^2) | 朴素DP、两重循环 |
| n≤10^4~10^5 | O(n log n) | 排序+二分、线段树、树状数组、堆 |
| n≤10^6 | O(n) | 线性扫、前缀和、线性筛 |
| n≤10^7以上 | O(n)都不一定稳 | 需要O(√n)或O(log n)的数学结论 |
这张表有个前提：时间限制通常是1秒，评测机是常规的C++环境。如果是2秒或3秒，上面的数据可以适当放宽。如果用Python，基本要再下降一个量级，n=10^5时O(n log n)都要小心再小心。
2.2 为什么log n小到经常被忽略
在表里的所有复杂度里，O(log n)是最被低估的，因为它的增长速度实在太慢了。n=10^6时，log_2 n≈20；n=10^9时，log_2 n≈30。哪怕n是宇宙里的原子数，log n也不过是几百。
这意味着什么？意味着如果你的算法是O(log n)（二分、树状数组、set/map的单次操作），配合一个前面乘的常数，在1秒内几乎是无敌的，可以放心处理10^9级别的数据。所以大量竞赛算法设计的目标，就是想办法把一个O(n)或O(n log n)的主逻辑通过预处理或数据结构降成O(log n)。
这也是很多优化题的思维起点：看到n=10^9，第一反应是这题不可能遍历所有东西，只能二分答案，或者用数学公式直接算。这种思维本质就是复杂度分析倒逼算法设计。
2.3 指数级复杂度的极端场景
O(2^n)和O(n!)是竞赛里的“核武器”，只在n特别小的时候用。n=20时2^20≈10^6，可以跑；n=30时2^30≈10^9，已经危险了；n=50时2^50根本不可能，但折半搜索可以把O(2^n)变成O(2^(n/2) * n)，n=50时约为2^25 * 50≈1.6×10^9，勉强可能过，这就是为什么n=50的题经常出现“meet in the middle”。
我见过不少选手拿到n=30的题直接放弃，觉得“这规模也太大了”，其实2^30虽然极限，但如果时间限制是3秒、常数又小，有些状态压缩DP是能过的。复杂度分析的价值就在这里：它能告诉你边界到底在哪里，而不是靠印象瞎猜。
3. 1秒时间限制到底能跑多少操作：估算方法论
3.1 基本操作数与常数因子的换算
很多人知道“1秒大概能跑10^8次操作”，但具体怎么用这个数，并不清楚。我给出一个更细致的参考基准（以C++、开O2优化、1秒限制为例）：
| 算法类型 | 1秒内安全的基本操作数 |
|---|---|
| 纯内存读写、简单算术 | 2×10^8 ~ 5×10^8 |
| 带数组索引的循环 | 1×10^8 ~ 2×10^8 |
| 有函数调用、分支判断较多的循环 | 5×10^7 ~ 1×10^8 |
| 带取模、除法运算的循环 | 1×10^7 ~ 5×10^7 |
| 使用STL容器（vector、map、set）的循环 | 1×10^6 ~ 1×10^7 |
注意，这里的“操作数”不是笼统的一句“这个算法要跑n次”，而是要估算内层循环每次迭代实际执行了多少加减乘除、比较、数组访问、函数调用。例如下面这段代码：
for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (a[i] + a[j] == target) ans++; } }内层判断里有加法运算、两个数组访问、一次比较，再加上循环自身的i、j维护，大概5~10个基本操作。n=10^5时总操作数约为n*(n-1)/2 * 8，约4×10^10，超出安全量级，直接就TLE了。n=10^4时总操作数约4×10^7，在安全区间里，可以过1秒限制。
3.2 递归、STL、快读这些隐藏开销怎么算
估算复杂度时，最容易漏掉的是常数和额外开销。有人写了个O(n log n)的归并排序，交上去竟然TLE，一看代码才发现他在递归里每次new了一个vector来合并。这样每次递归都有动态内存分配的开销，常数直接飙升好几倍，10^6个元素就卡出天际。
还有vector的push_back、map的单次操作，标称O(1)和O(log n)，但常数比裸数组大得多。同样O(n log n)的复杂度，用裸数组实现的快排比用multiset挨个插入快几倍到十几倍。所以估算时要问自己：这个复杂度的常数有多大？有没有隐藏的高开销操作？
输入输出也要算进去。cin不关同步的时候比scanf慢很多，大输入时只读数据就可能花掉大把时间。我实测过，n=10^6的整数输入用不关同步的cin要0.3~0.4秒，占掉1秒限制的三分之一还多，再用朴素算法基本必死。所以竞赛代码一般都会写快读或者用ios::sync_with_stdio(false); cin.tie(0);。
Python选手要特别注意：Python的常数因子比C++大20到50倍，即使复杂度阶数一样，1秒内能处理的数据范围也小得多。n=10^5时，O(n log n)的Python代码常见时间在0.5~1.5秒之间徘徊，经常需要优化到O(n)甚至O(n log n)但常数极小的写法才稳。
4. 空间复杂度：比想象中更容易翻车的第二道坎
4.1 内存上限与数据结构体积的换算方法
空间复杂度的计算比时间简单得多，核心就是统计所有全局数组、局部容器、递归栈占用内存的总和。先记住几个基本尺寸：
| 类型 | 大小 |
|---|---|
| char / bool | 1字节 |
| int | 4字节 |
| long long / double | 8字节 |
| float | 4字节 |
| 指针（64位系统） | 8字节 |
计算数组大小只要乘一下。比如int a[1005][1005]是1005×1005×4B≈4MB；long long dp[5005]是5005×8B≈40KB；int d[10005][10005]就达到400MB，即使内存限制是1GB也勉强，但如果限制是256MB就直接MLE。
竞赛里常见内存限制是64MB、128MB、256MB、512MB。用256MB举例，你可以快速心算：一个int二维数组开到8000×8000（约256MB）就爆了，所以二维数组一般安全范围是5000×5000（约100MB）。看到一个题要求n=10000的二维DP，用int dp[10000][10000]直接死，需要滚动数组或者分块压缩。
4.2 常见的MLE元凶
第一个元凶是“顺手开大数组”。很多人怕越界，随手开个int a[200005]或int a[300005]，没问题；但如果开int dp[1000005]，也就是4MB，通常也没问题。真正的问题是二维数组无脑[10005][10005]，400MB直接炸。我看到过一个题解用vector<vector<int>>开个10000×10000的二维vector，结果每个vector还有额外对象开销，比裸数组还要浪费几十MB。
第二个元凶是“递归深度”。递归在竞赛里很常用，但系统栈默认深度上限往往只有几百KB到几MB。深度超过几十万就会栈溢出，报错往往是MLE或RE而不是TLE。经典的C++递归深度到1e6左右大概率爆栈，所以深度优先搜索遍历一棵链状树时，如果数据让你递归1e5层，你需要改成显式栈，或者用尾递归优化不了就直接换写法。
第三个元凶是“STL容器长期持有内存”。vector.clear()不会释放内存，只会把size清零，capacity依然保留。你循环多次往vector里push_back，clear之后又push，内存一直在涨。如果每个case的vector开得很大，多组数据跑下来实际内存比预想高很多。真正释放要靠vector<int>().swap(v);。
还有一个经典案例：ST表（Sparse Table）。它存的是每个区间长度为2^k的最大值，数组大小是n×log_2 n。n=10^5时，约10^5×17×4B≈6.8MB，没问题；但如果n=10^6，就变成10^6×21×4B≈84MB，碰到64MB的限制就MLE。所以看到ST表的时候，先算一下这个量，再决定要不要换线段树。
空间复杂度和时间复杂度的关系常常是矛盾的。有的优化需要“空间换时间”，比如预处理前缀和、开多个辅助数组；但空间用多了又MLE。这两个数组是对立的，必须一边算一边权衡。
5. 一次完整实战：从TLE到AC的排查链路
5.1 题目场景与第一次提交
这里用一个非常经典的例题来讲排查思路。题面是：给定长度为n的整数数组a，有q次询问，每次询问区间[l,r]的最大值。限制：n,q≤10^5，时间1秒，内存64MB，数据保证所有数在int范围内。
初学者第一反应自然是“每次询问我遍历一下区间，取最大值”。这个逻辑完全正确，复杂度是O(nq)。n=10^5、q=10^5时，总操作数约10^10，按最乐观的每秒2×10^8次估算也需要50秒。提交后TLE是必然的。
这次TLE的价值不是让人气馁，而是提供了完整的决策依据：朴素算法毫无疑问超时了，接下来要往“更快地回答区间最大值”方向想。
5.2 逐层分析：复杂度天花板与算法选型
拿到这个题，先把数据范围摆出来：n和q都是10^5，时间1秒。按照第2节的表，能接受的复杂度上限大概是O((n+q) log n)。目标就变成了“预处理之后，每次询问O(log n)或O(1)”。
在这个思路下，有三条路：
- 线段树：建树O(n)，每次询问O(log n)。空间上开4n个int，约4×10^5×4B=1.6MB，非常安全。
- 树状数组：可以维护前缀最大值，但区间最大值用树状数组是错的，它只适合满足可减性的操作（如区间和、区间异或），最大值不能做差。
- ST表：预处理O(n log n)，每次询问O(1)。空间上n log n约10^5×17×4B≈7MB，在64MB下也安全。
实际操作中，我可能会先写ST表，因为编码简单，但前提是刚才算过空间够。如果这道题改成n=10^6且内存限制64MB，ST表84MB就会MLE，这时候就必须用线段树了。这就是空间复杂度如何反过来决定算法选型。
5.3 一步步排查：从TLE到AC的过程
我用线段树版本写出标准代码。
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int a[MAXN], tree[MAXN * 4]; void build(int node, int l, int r) { if (l == r) { tree[node] = a[l]; return; } int mid = (l + r) >> 1; build(node << 1, l, mid); build(node << 1 | 1, mid + 1, r); tree[node] = max(tree[node << 1], tree[node << 1 | 1]); } int query(int node, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return tree[node]; int mid = (l + r) >> 1; int res = 0; if (ql <= mid) res = max(res, query(node << 1, l, mid, ql, qr)); if (qr > mid) res = max(res, query(node << 1 | 1, mid + 1, r, ql, qr)); return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i]; build(1, 1, n); while (q--) { int l, r; cin >> l >> r; cout << query(1, 1, n, l, r) << '\n'; } return 0; }每次query递归访问树上的O(log n)个节点，总复杂度O((n+q)log n)，约10^5×17×2≈3.4×10^6次递归调用，时间和空间都安全。提交就能AC。
如果这时候仍然TLE，我要做的就是分步排查。第一步看输入规模：n和q都是10^5，cin关同步后没问题。第二步看是“整个程序慢”还是“查询慢”：如果只测建树不查询，多快；如果只查一次，多快；这样二分定位。第三步，如果递归次数太多导致栈开销过大，可以改非递归线段树或改用ST表。第四步，如果确实常数大到跑不过去，那就对每个query用循环实现的非递归版本，或者直接用ST表O(1)回答。
这种排查思路的本质就是：先用复杂度分析画出“可行域”，再在可行域里做法实现，最后如果速度不够，再把常数优化一点点挤出来。而不是看到TLE就盲目乱改循环、加register、甚至换编译器，这些都是没有信息量的无效操作。
6. 我踩过的复杂度相关的深坑和优化技巧
6.1 看上去O(n)其实O(n log n)的隐藏因子
这是最坑的一种，表面复杂度没问题，但里面藏了个log导致超时。最常见的就是在循环里使用std::map或std::set。很多人写代码时习惯性用std::map<int,int>存计数，没考虑每次map[]访问都是O(log n)。如果外层循环n=10^5，内层每个元素做一次map操作，实际是10^5×log(10^5)≈1.7×10^6次操作，勉强能过；但如果内层又套了一层循环，变成了n×n×log n，直接炸。
还有std::unordered_map。标称O(1)平均，但哈希碰撞严重时可能退化到O(n)，被精心构造的输入卡到TLE。竞赛里我见过专门卡unordered_map的题，所以大规模哈希计数，我宁可用数组离散化，或者用std::sort后直接扫一遍，一次排序O(n log n)也很可控。
另一个隐藏因子是memset。memset的时间是O(n)，但如果你在循环里对一个大数组反复memset，整体就会变成循环次数乘数组大小的复杂度。比如对每个测试点做memset(dp,0,sizeof(dp))，数组是10^5，测试点有100个，那就是10^7，还好；但数组是10^6，测试点有1000个，就是10^9，直接超时。很多多组数据题就是这么TLE的，不是算法的问题，是重置状态的方式太粗暴。
6.2 递归的深度是把双刃剑
递归是竞赛里最容易被忽略的复杂度来源。递归本身的栈开销不算在时间复杂度里，但深度过深会导致MLE或RE。经典的快排最坏情况是O(n^2)，递归深度到达n，再加上每次划分的常数，1e5的有序数据就能把递归版的快排卡死。这也就是为什么C++标准库的sort是混合排序，不只是裸快排。
我自己印象最深的一次是写Tarjan求强连通分量，递归深度等于节点数，图是链状的，1e5个节点直接爆栈。后来学乖了，拿到的代码里但凡有递归，总是先估算最坏递归深度：如果深度可能达到10^5以上，就考虑要么减少递归分支，要么改成显式栈，要么加栈空间编译指令但这个方法在线上评测时可不可靠，不要依赖。
6.3 用快读和输出优化省下的时间可以救命
很多选手低估了IO在总耗时里的占比。单次scanf/printf看起来很快，但当输入是10^6个整数时，时间不可忽略。我自己实测，10^6个整数用关闭同步的cin大概0.3~0.4秒，用快读getchar自己解析整数大概0.1~0.2秒，差距虽然不到0.3秒，但在时间限制1秒的题里可能就是AC和TLE的分界线。
输出同理，endl除了换行还会强行flush，非常慢；用'\n'能快很多。大批量输出时最好统一存到字符串或直接用printf批量输出。一个总原则：IO绝对不能成为算法复杂度之外的第二个瓶颈，把它当成复杂度的一部分去估算。
// 快读模板，实测比 cin/scanf 在大量整数输入时更快 inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); } return x * f; }6.4 空间换时间的时候，先把空间账算清楚
用ST表、预处理前缀、记忆化搜索这些“空间换时间”策略前，如果不先把空间算明白，就容易出现MLE。我见过最哭笑不得的案例是：写记忆化搜索时用了map<pair<int,int>, int>做DP缓存，维度稍微一大，map对象本身的额外开销比裸数组大几倍，直接MLE。
正确的做法是，先根据状态规模选择一个紧凑的存储结构。二维DP通常用vector<vector<int>>或裸数组，三维以上用压平的一维数组，把编号算成i * m + j的形式。这样既快又省空间。
再举一个具体的平衡案例：求前缀和时，如果要用二维前缀和，int sum[1005][1005]就是4MB，安全；但int sum[10005][10005]是400MB，直接爆。这时要想办法降维：只存每一行的前缀和，然后按行累加；或者用差分数组多次处理。空间复杂度分析在这里直接决定代码怎么写。
7. 最后再说几句我自己的习惯
我现在拿到一道题，第一步永远是看数据范围，然后在草稿纸上写三行：这题的n最大是多少；朴素算法的复杂度是多少；最坏情况下要执行多少次基本操作。这个流程只需要一分钟，但能帮我过滤掉九成不该写的暴力。
同样，写完一份代码，提交前我也会花十秒钟估算一下空间：所有全局数组加起来的字节数是多少，递归深度会不会爆栈，每个vector到底装了多少东西。这个习惯曾经帮我避开了好几次MLE，尤其是那种“本地跑得好好的，一提交就内存报错”的情况。
学弟学妹经常问我：“怎么才能一眼看出这题要什么复杂度？”答案其实很简单——多算。算多了之后，看到n=10^5就知道不可能O(n^2)，看到n=10^9就知道必须O(log n)或O(√n)，看到n=20就知道可以想状态压缩。这些判断不是天赋，是熟练度。
如果这篇文章能让你下次看到TLE或MLE时，第一反应不再是“我的代码出bug了”，而是“先算算我的算法复杂度到底是多少”，那它就没白写。比赛里时间宝贵，把复杂度分析的功夫花在写代码之前，永远比在超时之后乱试划算得多。
