时间复杂度和空间复杂度实战指南：从大O记号到优化决策

我刚开始学数据结构那阵子，第一道把我卡死的题目不是链表反转，也不是二叉树遍历，而是一道看起来“平平无奇”的数组求和：给一个长度为 n 的数组，输出所有连续子数组的和。我用了三层 for 循环，自己测试 n=100 的时候跑得飞快，心里还挺得意。结果一交到评测系统，数据规模直接拉到 n=100000，运行超时四个字明晃晃挂在屏幕上。那一刻我才意识到，程序跑得快不快，跟你机器好不好、代码写得“紧凑”不紧凑关系不大，真正决定成败的，是你选的算法随数据规模增长时的表现。这个表现，就是数据结构第一课就要面对的时间复杂度和空间复杂度。

这篇内容没什么玄乎的，就是把这些年我自己手算复杂度、调超时、优化空间踩过的坑捋一遍。适合刚开始学数据结构的人，也适合刷题总卡常数、或者写代码从不考虑资源占用的朋友。我不打算照本宣科背定义，而是从实际问题出发，告诉你复杂度到底咋算、为啥这么算、算完又怎么用。

1. 复杂度在度量什么：不是计时，是增长趋势

1.1 程序慢不是电脑的问题

很多人有个直觉：程序超时，换台好电脑不就完了？事实是，评测系统的机器通常是固定配置，你写个 O(n²) 的代码，数据规模翻一倍，耗时就要翻四倍。你以为换电脑能把四倍扛下来，可数据规模再翻一倍，就是十六倍。这时候多少硬件都救不回来。

复杂度的核心思想，是抛开机器主频、编译器优化、语言差异等“外部噪音”，只盯着一个问题：输入规模 n 变大的时候，算法需要执行的“基本操作次数”跟着怎么变。这个变化趋势，才是算法的内禀属性。

打个比方，你开了一家快递分拣站。方案A是：n 件快递来了，每个人都去翻一遍全站的快递单，才能确认自己负责的那件在不在。那么工作量大概是 n × n，也就是 n²。方案B是：每件快递进门直接分区投放，找一件只需看一眼分区标签，工作量大概就是 n。你给方案B加再多人手、再好的传送带，它也不会变成 n 的一次方，而方案A即使加一百个人，只要分拣逻辑还是“全站扫描”，它依然是 n² 级别的增长。

1.2 大O记号：扔掉细节，只看主部

我们引入大O记号（Big O notation）。它的严格定义用数学语言说就是：存在常数 c 和 n₀，使得当 n ≥ n₀ 时，T(n) ≤ c·f(n)，那么就说 T(n) = O(f(n))。

听着绕，用大白话讲：当 n 足够大的时候，你的算法操作次数 T(n) 肯定不超过某个常数倍的 f(n)。所以 f(n) 就是一个“天花板”。

举个例子，你数了一段代码，发现它总的操作次数是：

T(n) = 3n² + 2n + 10

按照大O记号，直接圈定最高次项 n²，把前面的系数 3 扔了，把后面的 2n 和 10 也扔了，最后写成 O(n²)。为什么能这么扔？因为当 n 很大的时候，n² 是绝对的主力，3 倍也好、2n 也好，都不改变“增长形态”。

你可以把大O理解为“摘要”。就像你想了解一个人的收入水平，只需要知道他处于“年入百万”这个档次，而不必纠结是100万还是120万。复杂度同理，它想表达的就是这个算法在数据规模足够大的时候，属于哪个“档次”。

1.3 常数项和低阶项为什么必须扔掉

这个“扔掉”不只是为了书写简单，它有实际意义。T(n) = 3n² 和 T(n) = 100n² 在 n 足够大的时候，都逃不过“平方级”的宿命。反过来，哪怕 T(n) = 1000n，也比 T(n) = n² 强得多——你只要让 n 超过1000，线性就比平方快，而且越甩越远。

所以分析复杂度的时候，我会先画一个“框”：找到代码里执行次数最多的那条语句，看它执行次数和 n 的关系。比如下面这段：

int sum = 0; for (int i = 0; i < n; i++) { sum += i; }

执行次数最多的就是sum += i，一共 n 次。所以整个循环是 O(n)。这比你去数每一行指令、考虑分支预测、缓存命中要干净利落得多。

有人会说，那系数大难道不影响实际慢吗？影响，但那是“常数优化”的范畴。工程里常数大的 O(n) 可能跑不过常数极小的 O(n²)，这时候需要实际测试。但做算法分析、设计系统初版方案时，我们优先保住“增长形态”，因为 n 早晚会大到让常数失去意义。这也是为什么面试官问复杂度时，最在意的是你方案属于哪个“档”。

2. 时间复杂度手算指南：从循环到递归的逐层拆解

2.1 数循环次数：一重、双重、三重

手算复杂度的基本功，就是数循环到底执行了多少轮。先看最简单的一重循环：

for (int i = 0; i < n; i += 2) { // do something O(1) }

每次 i 加 2，循环次数是 n/2。根据大O记号的规则，系数 n/2 里的 1/2 直接扔掉，所以依然是 O(n)。

再看双重循环：

for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // do something O(1) } }

内层循环每次跑 n 次，外层跑 n 次，总共 n × n = n² 次，所以是 O(n²)。

但如果内层循环的边界跟着外层变：

for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { // do something O(1) } }

内层执行次数是 0 + 1 + 2 + ... + (n-1) = n(n-1)/2，保留最高次项，依然是 O(n²)。很多人看到“内层次数少了”，以为复杂度会降级，其实没有。少掉的只是一半，系数而已，增长形态没变。

三重循环同理，最典型的三重 O(n³) 就是三个从 0 到 n 的循环嵌套。只要最内层代码是常数时间，层数就是幂次。这个规律可以记一下：k 重循环嵌套，每一重都完整跑 n 次，基本就是 O(nᵏ)。

2.2 每轮减半的循环：为什么是 log₂n

循环复杂度里最容易懵的，是这种写法：

int i = 1; while (i <= n) { i = i * 2; }

每执行一次，i 就翻倍。执行 k 次后，i = 2ᵏ。当 2ᵏ > n 时停止，所以 k ≈ log₂n。这个复杂度记作 O(log n)。

为什么不是“n/2”？因为减法循环每轮减一个固定值，执行 n/2 次；而乘法循环是每轮规模指数级缩小，执行次数是“需要翻多少倍才能超过 n”，那就是对数级。

对数级的增长有多慢？n = 10⁹ 的时候，log₂n 也才大约 30。一个 O(log n) 的算法在十亿级数据上可能不到五十步就跑完了，而一个 O(n) 算法要跑十亿步。所以见到“每次缩小一半”的搜索、跳表、二分等操作，第一反应就是对数级。

2.3 递归的时间复杂度：递归树和主定理的朴素用法

递归的复杂度不能只看循环次数，要看“递归调用了多少次”以及“每次调用做了多少工作”。最简单的办法是画递归树。

拿常见的斐波那契递归举例：

int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }

这个递归树是一棵二叉树，树的层数大约是 n，每一层节点数最多接近 2ᵏ，整棵树的节点总数是 2⁰ + 2¹ + ... + 2ⁿ⁻¹ = 2ⁿ - 1。所以这个写法的时间复杂度是 O(2ⁿ) —— 指数级，n 到 40 左右就已经慢到让人崩溃。这就是教科书上为什么不推荐用这种递归求斐波那契的原因。

另一类常见递归是“每次只调用一次，规模减半”：

void func(int n) { if (n <= 0) return; func(n / 2); // do something O(1) }

这里的递归链长度是 log₂n，每层做常数工作，所以是 O(log n)。

再复杂一点的递归，比如归并排序，每次把规模分成两半，每一层合并要做 O(n) 的工作，递归树有 log₂n 层，总复杂度就是 O(n log n)。

如果你不想每次画树，可以用一个简化版主定理：形如 T(n) = aT(n/b) + O(nᵈ) 的递归式，如果 nᵈ 增长快，则复杂度是 O(nᵈ)；如果两者相当，则是 O(nᵈ log n)；如果递归部分增长更快，则是 O(n^log₃a)。这个口诀够应付大多数课程和面试，真遇到极端情况再回头翻主定理严格形式。

2.4 常见复杂度排名表

我把算法设计里经常打交道的复杂度按“快慢”排了个表，你可以把它当字典查：

实际评估的时候，我会把“允许的执行次数”大概框一下：如果 1 秒内要跑完，普通机器的常数表现大概能承受 10⁸ 次简单操作。如果你的算法是 O(n²)，那么 n 最多到 10⁴；如果是 O(n log n)，n 能到 10⁶ 甚至 10⁷。这个经验值帮我在拿到题目的一瞬间就能判断思路是否可行。

3. 空间复杂度：被很多人忽略的第二条命脉

3.1 空间复杂度怎么数：输入不算，额外才算

时间复杂度过关不代表程序能跑。有些题卡的不是 CPU，而是内存。空间复杂度衡量的是：算法运行过程中，除了输入数据本身占用的存储之外，额外开辟了多少空间，随 n 如何增长。

比如你写了个函数，接收一个数组，然后新建了一个同样大小的数组来装中间结果，那额外的空间就是 O(n)。如果你只用了几个 int 变量，不管 n 多大，额外空间都是常数级别的 O(1)。

我在初学时经常搞混“输入数组算不算”。标准的空间复杂度只算“额外空间”，因为输入所占空间是题目给你的，不算你的算法开销。面试官问“你的方案空间复杂度多少”，答案通常都在“额外开没开数组/递归深度”上。

3.2 原地算法的真相：O(1)空间和交换变量

空间复杂度 O(1) 的算法常被称为“原地算法”。最经典的例子是数组翻转：

void reverse(vector<int>& nums) { int left = 0, right = nums.size() - 1; while (left < right) { swap(nums[left], nums[right]); left++; right--; } }

这里只用了 left、right 两个变量，外加 swap 时可能用到的一个临时变量，这些都不随 n 变化，所以空间复杂度 O(1)。

注意一个细节：如果把翻转的结果放到一个新数组里返回，空间复杂度就变成 O(n)。很多新手写题喜欢“新建一个数组把答案装进去”，这就是典型的空间复杂度下不去的原因。不是说不能那样做，而是要心里有数：你用了多少额外空间，是不是有更优的原地方案。

3.3 递归栈空间：n层递归真的不占空间吗

递归的空间复杂度是个重灾区。每调用一次函数，系统就要在调用栈上压入一层栈帧，保存参数、局部变量、返回地址。递归深度是 n，那栈空间就是 O(n)。

举个例子，递归求 1 到 n 的和：

int sum(int n) { if (n == 0) return 0; return n + sum(n - 1); }

虽然代码里没开任何数组，但因为递归要调用 n 层，空间复杂度是 O(n)。而循环累加只占 O(1) 空间。同样的功能，两种实现空间开销天差地别。

更危险的是递归深度过大可能直接爆栈。我遇到过某同学用递归写深度优先搜索，数据规模一上万，程序立刻崩溃，错误信息是栈溢出。他不是逻辑写错了，而是空间复杂度没有控制住。后面改成显式栈或者迭代，问题就解决了。

3.4 典型例子：归并排序的空间开销

光说理论没用，拿归并排序来算一笔：归并排序时间 O(n log n)，看起来很优秀，但它的合并阶段需要一个临时数组来归并两个有序子数组，临时数组的大小是 O(n)。再加上递归调用栈的 O(log n)，总体空间复杂度是 O(n)。

冒泡排序是原地排序，空间 O(1)，但时间 O(n²)。所以如果你内存吃紧，哪怕冒泡慢，也有它存在的理由。工程上内存和时间的权衡随时都在发生——比如在嵌入式设备上，你宁愿牺牲一些时间，也不愿让空间爆掉。这就是为什么复杂度永远要成对看，只看时间不看空间，方案常常是有偏的。

4. 复杂度分析中的经典误判与回避技巧

4.1 只看最内层代码，忽略函数调用本身

我见过的初级代码里，时间超时最隐蔽的原因之一，是把一段 O(n) 的代码当成 O(1) 来用。看起来你只是在循环里调了个“求数组长度”或“判断包含”的函数，但那个函数内部可能又遍历了一遍数组。比如下面这种：

for (int i = 0; i < n; i++) { if (find(vec.begin(), vec.end(), target) != vec.end()) { // ... } }

假设find是 O(n) 的线性查找，那整个循环就是 O(n²)。如果你没意识到find的代价，就会以为自己是 O(n)，结果提交后大数据疯狂超时。

正确做法：分析复杂度时，站在“抽象层次”上看，凡是调用标准库函数，先确认它内部的复杂度。C++ 的 vector 按索引访问是 O(1)，但 string 的 find 通常也是 O(n)；哈希表的插入删除平均 O(1)，但平衡树的插入删除是 O(log n)。库函数不是免死金牌，它只是把你的时间换了个地方花。

4.2 均摊复杂度：动态数组为什么插入是 O(1)

另一个容易让人困惑的概念是均摊复杂度。以动态数组（比如 Java 的 ArrayList 或 C++ 的 vector）为例，你反复在末尾追加元素，单次操作有时会触发扩容——重新分配一块更大的内存，并把旧元素全部拷贝过去，这一次开销是 O(n)。那动态数组的“push_back”到底算 O(1) 还是 O(n)？

答案是均摊 O(1)。推导方式是这样的：假设数组容量按 2 倍扩，那么每次扩容需要拷贝的元素数量是 1、2、4、8... 到 n 的过程中，所有扩容拷贝的总次数大约是 1 + 2 + 4 + ... + n ≈ 2n。把拷贝开销分摊到 n 次追加操作上，每次平均 2 次拷贝，是个常数。因此就算某一次操作特别慢，连续多次操作的总时间还是线性的。

这个思想提醒我们，分析复杂度不能只看单次操作的最坏情况，还要看连续操作的整体趋势。在面试里，那种“偶尔抽风但长期平均稳定”的结构，通常就要用均摊分析来解释。

4.3 最好/最坏/平均复杂度，不只背一个 O

标准的大O记号默认描述的是最坏情况的上界，但实际问题里，我们也常讨论最好情况和平均情况。快速排序是个典型：平均时间复杂度 O(n log n)，最坏情况却可能退化到 O(n²)——比如每次选的基准值正好是当前区间的最小值或最大值。

我以前面试某公司时，让候选人分析快速排序的复杂度，他说“快排是O(n log n)”。这个答案本身没错，但如果不区分“最坏/平均”，面试官就会追着问：输入已经有序时，快排还是O(n log n)吗？这时候如果回答“不一定”，就需要解释快排的退化原因。

我的建议是，自己写代码时至少要同时考虑三类输入：随机数据下的平均表现、最坏数据的退化风险、最好情况下的复杂度。不能因为平均复杂度好看，就忽略了某些极端输入可能把性能拖垮。比如用快排时加随机化基准，或者改用归并排序来稳定保证 O(n log n)，都是实际决策。

4.4 递归深度爆栈：复杂度没算错，栈却炸了

递归的空间复杂度算出来是 O(log n)，看起来不大，为什么还是爆栈？这里要注意，栈的大小不是只由复杂度决定的。递归深度达到几百万层时，哪怕每一层栈帧很小，也超过了系统默认栈空间。这就是我在前面提到的：空间复杂度 O(log n) 说的是“内存总量随 n 对数增长”，但 n 本身特别大的时候，实际深度照样可能超标。

遇到这种问题，常规处理是改成迭代或显式栈。显式栈本质上是在堆上模拟系统调用栈，堆空间通常远大于栈空间，也更好控制。我这边有个习惯：任何递归深度可能超过 10⁵ 的代码，先写一个迭代版本对比一下，别偷懒。

4.5 log 底数不重要，但 n 和 log 别搞混

在复杂度记号里，O(log₂n) 和 O(log₁₀n) 其实等价，因为底数不同只会差一个常数倍数，而大O正好忽略常数。所以写复杂度时可以直接写成 O(log n)，不需要纠结底数。

但要注意的是，不要把 O(n) 写成 O(log n)，这种错误往往发生在“循环一次后规模减半”和“遍历所有元素”两种场景交错时。我出过一道练习给朋友做，他写了个递归，每次把 n 减半，但每次递归里又要遍历一遍当前数组，结果他以为是 O(log n)，实际是 O(n log n)。原因就是每一层的 O(n) 工作不能凭空消失，递归或循环里每一层的工作量都要累加。

5. 从刷题到工程：复杂度选择的实战决策

5.1 用数据规模反推目标复杂度

我在拿到一个算法题时，第一件事不是写代码，而是扫一眼题目的数据范围。如果某个量级 n 最大是 10⁵，我脑海里立刻浮现：O(n²) 基本想都别想，O(n log n) 是安全区。如果 n 最大是 20，那我甚至可以考虑 O(2ⁿ) 的暴力搜索，因为 2²⁰ 大概也才一百万次操作。

这背后的逻辑就是前面提到的“1秒大约能跑 10⁸ 次操作”。我把这个经验值再细化一下：

这不是绝对真理，而是一个快速筛方案的参考。有人会问，现代机器跑 10⁹ 次也不是不行吧？能跑，但要考虑常数开销、内存访问、语言解释器等，稳妥起见我还是保守点。工程上做容量评估也一样，先估算请求量，再倒推允许的时间复杂度，最后选数据结构。

5.2 用空间换时间：熵一直都在

复杂度优化的核心思路无非两个：少做重复劳动，或者用空间换时间。哈希表就是空间换时间的典型代表：为了把查找从 O(n) 降到平均 O(1)，你额外维护一张表，空间通常 O(n)。在去重、缓存、计数等场景里，这个交换几乎永远划算。

还有一个值得说的例子是“前缀和”。假设你要反复查询数组里某个区间 [l, r] 的和，朴素做法每次 O(n)，查询 m 次就是 O(mn)。如果你提前算一个前缀和数组，每次查询就变成了 O(1)，预处理成本 O(n)。对于大量询问的场景，这是质变级的优化——把一次查询的时间从 n 压到 1，代价只是 O(n) 的额外空间。

空间换时间要注意“成本可控”。如果你已经用了 O(n²) 的空间来换 O(1) 的查询，在 n 上万时内存就爆炸了。所以换不换，要看业务场景里是时间稀缺还是空间稀缺。移动端、嵌入式往往是内存紧张，后端高并发往往是响应时间紧张，决策正好相反。

5.3 平时如何训练复杂度直觉

这部分是我个人的方法论。我刷题或看别人代码时，会刻意做三步走：

第一步，拿到代码先不运行，手写它的复杂度分析。是几重循环？循环变量增量是什么？有没有隐藏的递归？把每一段都标上 O，再组合出总体 O。

第二步，写一个数据规模测试脚本，故意把 n 调到理论值的边缘，看运行时间的增长倍数是否符合预期。比如 O(n) 的代码，n 从 10⁴ 到 10⁸ 增加一万倍，时间应该大约增长一万倍；而 O(n²) 的代码，n 从 10⁴ 到 10⁵ 增加十倍，时间应该增长一百倍左右。用这个办法，能纠正很多理论分析错误。

第三步，每次写完算法，强迫自己标注“最坏情况”和“额外空间”。哪怕只是在一个草稿本上写一句话，时间长了，遇到新问题就能条件反射地给出复杂度结论。我记得某位前辈跟我说过一句话：算法直觉不是天赋，是你被复杂度坑过足够多次以后形成的肌肉记忆。我深以为然。

5.4 一个综合练习：分析一段真实有坑的代码

最后放一道我经常让身边朋友分析的题目，你可以试着在纸上算一下：

int func(vector<int>& nums) { int n = nums.size(); int ans = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int sum = 0; for (int k = i; k <= j; k++) { sum += nums[k]; } ans = max(ans, sum); } } return ans; }

这是连续子数组最大和的暴力版：三重循环，第三层 k 最多从 i 到 j，整体执行次数大概是 Σ Σ (j-i+1)，折算下来是 O(n³)。空间复杂度是 O(1)，因为你没有额外数组。如果把它优化成前缀和版本，内层循环可以用 O(1) 的差值得出区间和，总体复杂度降到 O(n²)。再进一步用动态规划或者贪心（Kadane），可以做到 O(n) 时间、O(1) 空间。

从 O(n³) 到 O(n)，是三层循环一层层拆掉的过程。每一步都依赖你对“循环次数”和“额外存储”的精确把握。真正的复杂度能力就是这种从现象到本质的层层剥离。

我自己现在的习惯是，代码写完后先不急着提交，闭上眼想一遍复杂度：如果 n 变成十倍百倍，这段程序还能撑住吗？如果撑不住，问题出在哪个循环或哪次拷贝？把这个思考练成本能，比多背十个算法模板都管用。数据结构这条路很长，但时间复杂度和空间复杂度这两把尺子，是贯穿全程的度量衡——你可以暂时不会写红黑树，但你不能不知道，你打算暴力的那棵树到底要开多少栈、翻多少节点。