复杂度分析：时间复杂度、空间复杂度与均摊分析

很多人刚开始学数据结构时，最容易产生的一个感觉是：这些结构好像都能完成任务，那为什么还要专门比较它们？比如数组能存数据，链表也能存数据；排序能做，查找也能做；代码最后都能跑出来，那到底差别在哪里？

真正把这些结构区分开的关键，往往不是“能不能做”，而是“做这件事要花多大代价”。而复杂度分析，正是帮助我们衡量这种代价的基础工具。

学数据结构，如果不先建立复杂度意识，后面很多内容都会变成只记结论：知道哈希表查找快，知道二叉树高度重要，知道某些算法很高效，但并不真正明白“为什么高效”“快在哪里”“代价是什么”。所以复杂度分析不是一个可以随便略过的开场知识点，它几乎是后面所有结构与算法分析的共同语言。

一、为什么要学复杂度分析

写程序时，很多问题并不是“能不能做出来”，而是“数据规模一上来还能不能顶住”。

例如：

  • 在 10 条数据里查一个值，用遍历和用哈希表差别可能不明显；
  • 但在 1000 万条数据里查一次，差别就会非常明显；
  • 一个写法在样例上跑得很快，不代表在真实生产数据上也能撑住；
  • 有些程序逻辑看起来不复杂，但一旦嵌套循环太多，性能就会迅速恶化。

所以复杂度分析的核心意义，不是为了把 O(n)、O(log n) 这些符号背下来，而是为了让你在写代码时，能逐渐形成这种判断：

  • 这段代码最耗时的地方在哪里；
  • 当数据规模扩大 10 倍、100 倍时，性能会怎么变化；
  • 为了更快的时间复杂度，是否付出了更多空间代价；
  • 当前实现到底是“暂时够用”，还是“天然容易出问题”。

换句话说，复杂度分析训练的是一种面向规模的思维方式。

二、复杂度到底在衡量什么

复杂度本质上是在描述：

当输入规模不断增大时，程序运行所需资源会如何变化。

这里的“资源”，通常主要看两类：

  • 时间资源，也就是执行步骤大致如何增长；
  • 空间资源，也就是额外占用了多少内存。

所以最常见的两种复杂度就是：

  • 时间复杂度；
  • 空间复杂度。

注意，这里分析的不是某台机器上的精确秒数，也不是某次运行的精确内存字节数，而是一种更抽象、更稳定的增长趋势。

也正因为如此，复杂度分析的价值在于“跨环境比较”。不同机器性能可以差很多，但一个 O(n^2) 的算法，在数据规模变大后通常就是会比 O(n log n) 更容易吃亏，这种趋势不会因为机器换了就本质改变。

三、什么是时间复杂度

时间复杂度可以理解成：

一个算法的执行步骤数量，随着输入规模 n 增大，大致按什么规律增长。

这里最关键的不是精确数多少步，而是抓住“增长主项”。

比如下面这段代码：

1
2
for i in range(n):
    print(i)

如果循环执行 n 次，那么总体操作次数会和 n 成正比，所以时间复杂度可以记作 O(n)。

再看一个双层循环：

1
2
3
for i in range(n):
    for j in range(n):
        print(i, j)

外层执行 n 次，内层每次又执行 n 次，总操作次数大致是 n * n，所以时间复杂度是 O(n^2)。

如果是一种“不断折半”的过程，比如二分查找：

  • 每次都把问题规模缩小成原来的一半；
  • 经过若干次后问题规模降到 1；
  • 这样的增长趋势对应的就是 O(log n)。

所以时间复杂度的核心，不是死记定义，而是学会看出“这段代码的规模是线性增长、平方增长，还是对数增长”。

四、什么是大 O 表示法

平时说复杂度时，最常见的写法就是大 O 表示法，比如：

  • O(1)
  • O(log n)
  • O(n)
  • O(n log n)
  • O(n^2)

它描述的不是精确值，而是数量级上界中的主要增长趋势。

例如，一段代码总执行次数如果是：

1
3n + 2

当 n 很大时，常数 2 的影响可以忽略，系数 3 也不是重点，最关键的是它的主项是 n，所以复杂度记作 O(n)。

如果执行次数是：

1
2n^2 + 5n + 10

当 n 足够大时，真正主导增长的是 n^2，所以复杂度记作 O(n^2)。

所以使用大 O 时，通常遵循这样几条规则：

  • 忽略常数项；
  • 忽略低阶项；
  • 只保留最高阶主项；
  • 重点看输入规模变大后的增长趋势。

这也是为什么复杂度分析看起来“有点粗糙”，但其实非常有用。因为我们真正关心的，本来就不是小规模下多 3 步还是少 5 步，而是规模大起来之后会不会彻底失控。

五、常见时间复杂度应该怎么理解

下面这些复杂度是最常见的，也是学数据结构时必须逐渐形成直觉的部分。

1. O(1)：常数时间

表示无论数据规模多大，操作次数基本都不变。

典型例子：

  • 通过数组下标访问元素；
  • 栈顶入栈、出栈；
  • 哈希表平均情况下的查找。

注意，O(1) 不代表“只执行一步”，而是代表执行步数不会随着 n 增长而增长。

2. O(log n)：对数时间

表示每次操作都能显著缩小问题规模，常见于折半、分层和树高相关问题。

典型例子：

  • 二分查找；
  • 平衡二叉搜索树中的查找、插入、删除；
  • 堆的插入和删除。
3. O(n)：线性时间

表示问题规模扩大多少倍，执行步骤大致也扩大多少倍。

典型例子：

  • 遍历数组；
  • 顺序查找；
  • 在链表中找到某个位置。
4. O(n log n)：线性对数时间

这通常是很多高效排序算法的复杂度级别。

典型例子：

  • 归并排序；
  • 堆排序；
  • 快速排序的平均情况。
5. O(n^2)：平方时间

通常出现在双重遍历、两两比较等场景。

典型例子：

  • 冒泡排序；
  • 选择排序；
  • 某些朴素的嵌套比较问题。
6. 更高复杂度：O(n^3)、O(2^n)、O(n!)

这些复杂度在数据规模稍大时通常就会非常吃力。

典型场景：

  • 三重循环；
  • 某些暴力枚举；
  • 子集、排列相关的指数级搜索。

所以在实际问题中，很多优化的本质就是：

想办法把一个更差的复杂度，降到一个可接受的级别。

六、怎么从代码里分析时间复杂度

复杂度分析不是只会背结果，更重要的是能从代码结构里看出来。

1. 顺序结构：复杂度取加法后的主项

例如：

1
2
3
4
5
for i in range(n):
    print(i)

for j in range(n):
    print(j)

前一段是 O(n)，后一段也是 O(n)，总和是 O(2n)，最终记作 O(n)。

2. 嵌套循环：复杂度取乘法

例如：

1
2
3
for i in range(n):
    for j in range(n):
        print(i, j)

外层 n 次，内层每次 n 次，所以是 O(n^2)。

3. 循环次数不是固定 n 时，要看变量变化规律

例如：

1
2
3
i = 1
while i < n:
    i *= 2

每次翻倍，直到超过 n，所以执行次数大约是 log n，复杂度是 O(log n)。

4. 多层嵌套不一定就是 O(n^k)

例如：

1
2
3
4
for i in range(n):
    j = 1
    while j < n:
        j *= 2

外层是 n 次，内层是 log n 次，所以整体是 O(n log n)，而不是 O(n^2)。

5. 递归要看递归树或递推关系

递归复杂度一开始容易看不清，但本质也是在分析“总共做了多少层、每层做了多少工作”。后面讲递归时会进一步展开。

七、什么是最好、最坏、平均情况复杂度

同一个算法，在不同输入情况下，表现可能并不一样。

例如顺序查找：

  • 如果目标刚好在第一个位置，那几乎立刻找到；
  • 如果目标在最后一个位置，或者根本不存在，就要把整个数组扫完。

所以就会有三种常见视角：

1. 最好情况复杂度

在最理想输入下的表现。

2. 最坏情况复杂度

在最差输入下的表现。

3. 平均情况复杂度

在一般分布下的平均表现。

平时如果没有特别说明，我们说一个算法的时间复杂度，通常默认更关注最坏情况复杂度。因为它更稳妥，能帮助我们评估最保守的上界。

但在工程实践里，平均情况有时也非常重要。比如哈希表平均查找接近 O(1)，而快速排序平均复杂度是 O(n log n)，这些都是非常常见的工程判断依据。

八、什么是空间复杂度

空间复杂度描述的是：

一个算法在运行过程中，额外使用的存储空间会如何随着输入规模增长。

例如：

  • 如果只用了几个固定变量，那额外空间通常是 O(1)；
  • 如果额外开了一个长度为 n 的数组，那空间复杂度通常是 O(n)；
  • 如果递归深度为 n，调用栈也可能占用 O(n) 的空间。

要注意，空间复杂度看的是额外空间，不是把输入本身也重复算进去。

举个简单例子：

1
2
3
4
arr = [1, 2, 3, 4, 5]
sum_value = 0
for x in arr:
    sum_value += x

这里虽然输入数组本身有多个元素，但算法额外只用了一个 sum_value 和一个循环变量，所以额外空间复杂度是 O(1)。

再比如：

1
2
3
result = []
for x in arr:
    result.append(x * 2)

这里额外创建了一个和输入规模同级别的新数组，所以空间复杂度是 O(n)。

九、时间换空间，空间换时间是什么意思

在实际设计里，时间和空间经常需要权衡。

1. 时间换空间

意思是：

为了让程序更快，额外多使用一些内存。

典型例子：

  • 用哈希表加速查找；
  • 用缓存保存中间结果；
  • 用前缀和数组换取快速区间查询。
2. 空间换时间

这个说法口语里有时会混用，但更准确地讲，通常是“为了节省空间，接受更多时间开销”。

典型例子：

  • 不额外建索引，改用遍历查找；
  • 不保存中间状态，改为每次重新计算。

所以在做题或做工程时，不要只盯着时间复杂度，也要问一句：

这个性能提升，是不是以更高内存占用为代价换来的？

十、什么是均摊分析

均摊分析是很多初学者一开始最容易迷糊的地方。它解决的是这样一种情况：

某个操作平时很便宜，但偶尔会特别贵，应该怎么评价它的整体成本？

最经典的例子就是动态数组扩容。

假设一个数组容量满了之后，需要扩容成原来的 2 倍。扩容时要做的事情包括：

  • 申请一块更大的连续空间；
  • 把旧数组元素全部复制过去；
  • 再插入新元素。

这一次插入看起来可能要搬很多数据，代价像是 O(n)。但问题是：

  • 并不是每次插入都会扩容；
  • 大部分插入其实都很便宜，通常只是直接把元素放到尾部；
  • 把多次操作放在一起看，平均下来，每次插入的代价仍然是常数级。

所以动态数组尾插的均摊时间复杂度通常记作 O(1)。

这里的“均摊”不是统计意义上的平均输入，而是对一系列连续操作的总成本进行平摊。

也就是说，均摊分析关注的是：

  • 单次最坏可能很贵；
  • 但从长期连续执行看，平均到每次操作上仍然不高。

这个思想在很多结构里都很重要，不只是数组扩容，还包括某些懒更新、批量调整、路径压缩等技巧。

十一、一个关于均摊分析的直觉例子

可以把动态数组扩容想象成搬家。

  • 平时你只是把新东西放进房间里，成本很低；
  • 偶尔房间满了，就得换到更大的房子，搬一次家很贵；
  • 但如果每次都搬到更大的地方，那之后很长一段时间又都能轻松放东西。

所以虽然“某一次搬家”很累，但如果从长期看，每新增一件东西的平均代价其实没有那么夸张。

这就是均摊分析最值得抓住的直觉：

不要被某一次昂贵操作吓住，而要看它是不是被大量廉价操作稀释掉了。

十二、学习复杂度分析时最容易踩的坑

1. 把复杂度当成精确运行时间

复杂度只描述增长趋势，不等于某次运行一定花多少毫秒。

2. 只会背结论，不会从代码分析

真正要练的是看到代码结构后，能自己判断主项，而不是只会背“冒泡排序是 O(n^2)”。

3. 看到多层循环就直接判 O(n^2)

要先看每层循环的真实次数，不能机械套公式。

4. 忽略空间复杂度

很多人只盯着时间，其实在工程里，内存占用同样可能成为瓶颈。

5. 把均摊分析和平均情况复杂度混为一谈

两者不是一个概念。平均情况是在不同输入分布下取平均，均摊分析是在一系列操作上平摊总体成本。

十三、为什么复杂度分析是后面所有内容的底座

后面学数组、链表、栈、队列、树、堆、哈希表、图时，你几乎每次都会反复问这些问题：

  • 查找快不快；
  • 插入和删除代价大不大；
  • 是否需要额外辅助空间；
  • 数据规模大起来后还能不能撑住；
  • 为什么这个结构比另一个结构更适合当前问题。

这些判断，最终都离不开复杂度分析。

可以说，如果没有复杂度意识，数据结构会变成一堆互相独立的知识点；而有了复杂度意识之后，这些结构才会真正被一条统一的逻辑串起来。

总结

复杂度分析的价值，不在于记住几个符号，而在于帮你建立“面向规模思考”的能力。真正值得先建立起来的，是这些核心认识：

  • 时间复杂度描述的是执行步骤随输入规模增长的趋势；
  • 空间复杂度描述的是额外存储开销随输入规模增长的趋势；
  • 大 O 关注的是主项，而不是常数和细枝末节；
  • 写代码时要学会从顺序、嵌套、折半、递归这些结构里看出复杂度；
  • 均摊分析关注的是一系列操作的整体成本，而不是单次最坏值；
  • 真正的目标不是背公式，而是在遇到问题时能判断“这个实现是否足够高效”。

把这一篇理解透之后，后面再去学顺序表、链表、树、堆、哈希表和图，就会更容易明白：为什么这些结构的差异，本质上常常就体现在时间和空间复杂度的不同取舍上。

参考资源：