我以前的文章主要都是讲解算法的原理和解题的思维，对时间复杂度和空间复杂度的分析经常一笔带过，主要是基于以下两个原因：
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 表示法
Big O 记号的数学定义：
O(g(n)) = { f(n): 存在正常量 c 和 n_0，使得对所有 n ≥ n_0，有 0 ≤ f(n) ≤ c*g(n) }
我们常用的这个符号 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 记号表示法的讲解就够用了。
非递归算法分析
非递归算法的空间复杂度一般很容易计算，你看它有没有申请数组之类的存储空间就行了，所以我主要说下时间复杂度的分析。