算法时空复杂度分析实用指南

我以前的文章主要都是讲解算法的原理和解题的思维，对时间复杂度和空间复杂度的分析经常一笔带过，主要是基于以下两个原因：

1、对于偏小白的读者，我希望你集中精力理解算法原理。如果加入太多偏数学的内容，很容易把人劝退。

2、正确理解常用算法底层原理，是进行复杂度的分析的前提。尤其是递归相关的算法，只有你从树的角度进行思考和分析，才能正确分析其复杂度。

鉴于现在历史文章已经涵盖了所有常见算法的核心原理，所以我专门写一篇时空复杂度的分析指南，授人以鱼不如授人以渔，教给你一套通用的方法分析任何算法的时空复杂度。

本文会篇幅较长，会涵盖如下几点：

1、利用时间复杂度反推解题思路，减少试错时间。

2、时间都去哪儿了？哪些常见的编码失误会导致算法超时。

3、Big O 表示法的几个基本特点。

4、非递归算法中的时间复杂度分析。

5、数据结构 API 的效率衡量方法（摊还分析）。

6、递归算法的时间/空间复杂度的分析方法，这部分是重点，我会用动态规划和回溯算法举例。

在讲解复杂度的概念和具体计算方法之前，我先说一些实战中常见的技巧和容易踩的坑。

借助复杂度反推解题思路

举例来说吧，比如一个题目给你输入一个数组，其长度能够达到 10^6 这个量级，那么我们肯定可以知道这道题的时间复杂度大概要小于 $O(N^2)$，得优化成 $O(NlogN)$ 或者 $O(N)$ 才行。因为如果你写的算法是 $O(N^2)$ 的，最大的复杂度会达到 10^12 这个量级，在大部分判题系统上都是跑不过去的。

为了把复杂度控制在 $O(NlogN)$ 或者 $O(N)$，我们的选择范围就缩小了，可能符合条件的做法是：对数组进行排序处理、前缀和、双指针、一维 dp 等等，从这些思路切入就比较靠谱。像嵌套 for 循环、二维 dp、回溯算法这些思路，基本可以直接排除掉了。

再举个更直接的例子，如果你发现题目给的数据规模很小，比如数组长度 N 不超过 20 这样的，那么我们可以断定这道题大概率要用暴力穷举算法。

因为判题平台肯定是尽可能扩大数据规模难为你，它一反常态给这么小的数据规模，肯定是因为最优解就是指数/阶乘级别的复杂度。你放心用 回溯算法 招呼它就行了，不用想别的算法了。

所以说啊，很多读者看题都不看那个数据规模，上来就闷声写代码，这是不对滴。你先把题目给的所有信息都考虑进去，再写代码，这样才能少走弯路。

由于编码失误导致复杂度异常

这部分主要总结一下大家（尤其是初学者）在写代码时容易犯的一些编码层面的错误。这些错误会产生预期之外的时间消耗，拖慢你的算法运行，甚至导致超时。

使用了标准输出

在写算法题时，我们可能会用到 print/console.log 函数来打印一些状态，以便调试算法。

但你准备提交代码时，记得把这些输出语句注释掉，因为标准输出属于 I/O 操作，会很大程度上拖慢你的算法代码运行。

错误地「传值」而非「传引用」

比如 C++ 里面，函数参数默认是传值的，比如你传入一个 vector 参数，那么这个数据结构会被完整地复制一份，导致额外的时间和空间消耗。尤其是当这个函数是个递归函数的时候，错误地传值几乎必然导致超时或超内存。

正确的做法是传引用，比如 vector<int>&，这样就不会产生额外的复制开销。使用其他语言的读者可以自查是否存在类似的问题，一定要搞清楚你的编程语言的参数传递机制。

接口对象的底层实现不明

这应该算是一个比较刁钻的问题，一般在 Java 这种面向对象的语言出现，出现地比较少，但也必须引起注意。

Java 中 List 是一个接口，它有很多实现类，比如 ArrayList、LinkedList 等等。如果你学了基础知识章节的 手把手带你实现动态数组 和 手把手带你实现双链表，就知道 ArrayList 和 LinkedList 的很多方法复杂度不同，比如 ArrayList 的 get 方法是 $O(1)$，而 LinkedList 的 get 方法是 $O(N)$。

那么如果函数参数给你传入一个 List 类型的参数，你敢不敢直接 list.get(i) 进行随机访问？不敢吧。

这种情况，一般需要自己创建一个 ArrayList，把传入的 List 的元素全部复制过去，再通过索引进行访问，这样比较保险。

主要就上面这几个吧，它们都是非算法思想层面的问题，大家留心注意一下应该没什么问题。下面开始正式讲解算法复杂度分析。

Big O 表示法

我们常用的这个符号 O（大写字母 o，不是数字 0）其实代表一个函数的集合，比如 $O(n^2)$ 代表着一个由 g(n) = n^2 派生出来的一个函数集合；我们说一个算法的时间复杂度为 $O(n^2)$，意思就是描述该算法的复杂度的函数属于这个函数集合之中。

理论上，你看明白这个抽象的数学定义，就可以解答你关于 Big O 表示法的一切疑问了。

但考虑到大部分人看到数学定义就头晕，我给你列举两个复杂度分析中会用到的特性，记住这两个就够用了。

1、只保留增长速率最快的项，其他的项可以省略。

首先，乘法和加法中的常数因子都可以忽略不计，比如下面的例子：

O(2N + 100) = O(N)
O(2^(N+1)) = O(2 * 2^N) = O(2^N)
O(M + 3N + 99) = O(M + N)

当然，不要见到常数就消，有的常数消不得，可能会用到我们中学学过的指数运算法则：

O(2^(2N)) = O(4^N)

除了常数因子，增长速率慢的项在增长速率快的项面前也可以忽略不计：

O(N^3 + 999 * N^2 + 999 * N) = O(N^3)
O((N + 1) * 2^N) = O(N * 2^N + 2^N) = O(N * 2^N)

以上列举的都是最简单常见的例子，这些例子都可以被 Big O 记号的定义正确解释。如果你遇到更复杂的复杂度场景，也可以根据定义来判断自己的复杂度表达式是否正确。

2、Big O 记号表示复杂度的「上界」。

换句话说，只要你给出的是一个上界，用 Big O 记号表示就都是正确的。

比如如下代码：

for (int i = 0; i < N; i++) {
    print("hello world");
}

如果说这是一个算法，那么显然它的时间复杂度是 $O(N)$。但如果你非要说它的时间复杂度是 $O(N^2)$，理论上讲是可以的，因为 O 记号表示一个上界嘛，这个算法的时间复杂度确实不会超过 N^2 这个上界呀，虽然这个上界不够「紧」，但符合定义，所以理论上说也没毛病。

上述例子太简单，非要扩大它的时间复杂度上界显得没什么意义。但有些算法的复杂度会和算法的输入数据有关，没办法提前给出一个特别精确的时间复杂度，那么在这种情况下，用 Big O 记号扩大时间复杂度的上界就变得有意义了。

比如前文 动态规划核心框架 中讲到的凑零钱问题的暴力递归解法，核心代码框架如下：

// 定义：要凑出金额 n，至少要 dp(coins, n) 个硬币
int dp(int[] coins, int amount) {
    // base case
    if (amount <= 0) return;
    // 状态转移
    for (int coin : coins) {
        dp(coins, amount - coin);
    }
}

当 amount = 11, coins = [1,2,5] 时，算法的递归树就长这样：

后文会具体讲递归算法的时间复杂度计算方法，现在我们先求一下这棵递归树上的节点个数吧。

假设金额 amount 的值为 N，coins 列表中元素个数为 K，那么这棵递归树就是一棵 K 叉树。但这棵树的生长和 coins 列表中的硬币面额有直接的关系，所以这棵树的形状会很不规则，导致我们很难精确地求出树上节点的总数。

对于这种情况，比较简单的处理方式就是按最坏情况做近似处理：

这棵树的高度有多高？不知道，那就按最坏情况来处理，假设全都是面额为 1 的硬币，这种情况下树高为 N。

这棵树的结构是什么样的？不知道，那就按最坏情况来处理，假设它是一棵满 K 叉树好了。

那么，这棵树上共有多少节点？都按最坏情况来处理，高度为 N 的一棵满 K 叉树，其节点总数为等比数列求和公式 (K^N - 1)/(K - 1)，用 Big O 表示就是 $O(K^N)$。

当然，我们知道这棵树上的节点数其实没有这么多，但用 $O(K^N)$ 表示一个粗略的上界是没问题的，也很容易看出来这是一个指数级的算法，需要想办法优化运行效率。

所以，有时候你自己估算出来的时间复杂度和别人估算的复杂度不同，并不一定代表谁算错了，可能你俩都是对的，只是是估算的精度不同。

理论上，我们当然希望得到一个比较准确比较「紧」的上界，但想得到准确的上界对数学的功力有一定要求，我们针对面试刷题的话不妨退而求其次，只要数量级（线性/指数级/对数级/平方级等）能对上就没问题。

在算法领域，除了用 Big O 表示渐进上界，还有渐进下界、渐进紧确界等边界的表示方法，有兴趣的读者可以自行搜索。不过从实用的角度看，以上对 Big O 记号表示法的讲解就够用了。

非递归算法分析

非递归算法的空间复杂度一般很容易计算，你看它有没有申请数组之类的存储空间就行了，所以我主要说下时间复杂度的分析。