算法
算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。
主要还是从算法所占用的「时间」和「空间」两个维度去考量。
- 时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。
- 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。
什么是时间复杂度，如何表示？
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
常见时间复杂度：
| 时间复杂度 | |
|---|---|
| O(1) | 常数复杂度 |
| O(logn) | 对数复杂度 |
| O(n) | 线性时间复杂度 |
| O(n^2) | 平方复杂度 |
| O(n^3) | 立方复杂度 |
| O(2^n) | 指数复杂度 |
| O(n!) | 阶乘复杂度 |
主定理
在算法分析中，主定理（Master Theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。
——维基百科
主定理可以用来分析递归算法的时间复杂度（也叫渐进复杂度）。
常见时间复杂度问题分析
- 看一段代码根据n的不同情况，运行多少次。
- 画出递归状态树，第一层1个节点，第二层2个节点，第三层2^2个节点，第四层2^3个节点，最终根据等比数列求和公式计算所有的节点数，就是它的时间复杂度。
二叉树遍历，前序、中序、后序：时间复杂度是多少？
遍历二叉树，每个节点都会访问一次，所以最终时间复杂度都为O(n)，n代表节点总数。
也可以通过主定理推算出来。
图的遍历，时间复杂度是多少？
遍历图的时候，每个节点都会访问一次，所以时间复杂度都是O(n)，n代表节点总数。
搜索算法，DFS、BFS时间复杂度是多少？
无论是深度优先搜索还是广度优先搜索，每个节点都会遍历一次，最终的时间复杂度是O(n)，n代表节点总数。
二分查找，时间复杂度是多少？
二分查找，时间复杂度是O(logn)，n代表节点总数。
数组的时间复杂度？
| 操作 | 时间复杂度 |
|---|---|
| 头部追加 | O(n) |
| 尾部追加 | O(1) |
| 查找元素 | O(1) |
| 插入元素 | O(n) |
| 删除元素 | O(n) |
链表的时间复杂度？
| 操作 | 时间复杂度 |
|---|---|
| 头部追加 | O(1) |
| 尾部追加 | O(1) |
| 查找元素 | O(n) |
| 插入元素 | O(1) |
| 删除元素 | O(1) |
跳表的时间复杂度？
跳表处理的是有序链表，被称为“跳跃链表”。跳表的空间复杂度为O(n)。
| 操作 | 时间复杂度 |
|---|---|
| 头部追加 | O(logn) |
| 尾部追加 | O(logn) |
| 查找元素 | O(logn) |
| 插入元素 | O(logn) |
| 删除元素 | O(logn) |
空间复杂度
- 1.数组的长度
- 2.递归的深度
如果程序里面开辟了数组，空间复杂度就是O(n)，如果开启的是二维数组，空间复杂度是O(n^2)。如果程序用到了递归，则递归的最大深度就是程序的空间复杂度。如果又开辟了数组又有递归，则空间复杂度为数组长度和递归最大深度之中的较大值。
参考链接
主定理与递归程序时间复杂度的计算
算法的时间复杂度和空间复杂度-总结
跳表──没听过但很犀利的数据结构
算法的时间与空间复杂度（一看就懂）