复杂度：时间与空间

第 2 章 · 数据结构与算法

先问一个问题。 你说「这个算法快」、他说「那个算法慢」——到底快多少、慢多少？如果数据量从 100 变成 100 万，有的算法只是多干一点活，有的却会直接卡死。我们需要一把统一的尺子，既能描述「做了多少事」，又能描述「占了多少地方」，还能在数据变大时预判算法的表现。这把尺子就是复杂度，用大 O 表示法来写。学完这一章，你就能看懂别人说的 O(n)、O(n²) 是什么意思，也会自己判断一个算法「好不好」。

一、时间复杂度：做了多少「步」

程序运行时会执行很多条语句。我们把「读一个数、比较一次、赋值一次」这类基本操作算成一步。时间复杂度描述的是：当输入规模（比如数组长度）为 n 时，算法大概要执行多少步。

例如：在长度为 n 的数组里逐个查找某个数，最坏要比较 n 次，我们就说步数和 n 成正比；二分查找每次砍掉一半，步数大约为 log₂n。n 越大，这两种做法的差距就越大——时间复杂度就是在描述「步数随 n 怎么长」。

二、大 O 表示法：只看「量级」

我们并不关心精确的步数（比如 3n + 5），只关心随着 n 变大，步数大致按什么量级增长。大 O 就是用来表示这个量级的：

忽略常数：100n 和 n 都写成 O(n)；
忽略低阶：n² + n 只保留 n²，写成 O(n²)；
只保留「增长最快」的那一项，表示上界（最坏大概就这样）。

这样，我们就能用 O(1)、O(log n)、O(n)、O(n²) 等来统一描述算法，方便比较。

三、常见时间复杂度一览

下面这些是你会反复遇到的量级，从「几乎不随 n 变」到「随 n 爆炸」排个序：

O(1)

常数

数组按下标取数、哈希表按 key 查

O(log n)

对数

二分查找、平衡树查找

O(n)

线性

遍历数组、单次线性查找

O(n log n)

线性对数

归并排序、快排（平均）

O(n²)

平方

双重循环遍历、冒泡排序

O(2^n)

指数

暴力枚举子集（慎用）

常见时间复杂度：从左到右，随 n 增长越来越「费」

表示	读法	典型场景
O(1)	常数时间	下标访问、哈希查找
O(log n)	对数时间	二分、平衡树
O(n)	线性时间	遍历、单遍扫描
O(n log n)	线性对数	高效排序
O(n²)	平方时间	双重循环、简单排序
O(2^n)	指数时间	暴力枚举，n 大时易卡死

四、增长曲线：一眼看出谁更「陡」

下面这张图画的是：当横轴 n 增大时，不同复杂度的「步数」怎么长。曲线越陡，数据一大就越吃力。

时间复杂度随 n 的增长：O(1) 最平，O(n²) 最陡

五、O(n) 和 O(n²) 差多少？看动画

当 n 从 10 变到 100、再变到 1000 时，O(n) 的步数只是线性增加，O(n²) 却会暴增。下面两条 bar 随「时间」模拟 n 增大时步数的相对变化（循环播放）：

n 增大时，步数相对大小

O(n)

少

O(n²)

多

动画模拟：n 从小变大时，O(n²) 那条会很快超过 O(n)，数据量一大差距更明显。

同一段时间内：O(n) 增长平缓，O(n²) 增长迅猛

小贴士： 面试和实际写代码时，先看数据规模。n 在 10^5 以内，O(n²) 可能还能接受；到 10^6、10^7，就要尽量用 O(n log n) 或更好的算法，否则很容易超时。

六、空间复杂度：占了多少「地方」

除了时间，算法还会占用内存。空间复杂度描述的是：除了输入数据本身，算法还需要多少额外空间（变量、数组、递归栈等）。同样用大 O 表示。

O(1)：只用几个变量，不随 n 变，叫「原地」。
O(n)：额外开一个长度为 n 的数组，或递归深度为 n。
O(n²)：例如开 n×n 的二维数组。

很多时候我们会用多一点空间换时间（比如哈希表），或者用多一点时间省空间（比如原地排序）。时间和空间常常是权衡关系。

七、最好、最坏、平均

同一个算法，在不同输入下表现可能不同。例如在数组里线性查找：要找的数在第一个，就 1 步（最好）；在最后一个，要 n 步（最坏）；平均下来大约 n/2 步，量级还是 O(n)。

我们通常更关心最坏和平均：最坏能保证「再差也不会超过这个」；平均更接近实际体验。大 O 一般按最坏或平均来写，看约定。

八、小结

时间复杂度看「步数随 n 怎么长」，空间复杂度看「额外空间随 n 怎么长」。用大 O表示量级，忽略常数和低阶。O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n)，越往右越「费」。选算法时先估一下 n 有多大，再选合适量级的算法。下一章我们会从最基础的数据结构——数组与字符串——开始，并继续用复杂度来衡量各种操作。