一、时间复杂度

Big O notation时间复杂度 指函数或者代码 根据n的不同情况，运算了多少次。
O(1): Constant Complexity 常数时间复杂度
O(log n): Lograithmic Complexity 对数时间复杂度‘
O(N): Linear Complexity 线性时间复杂度
O(N^2): N square Complexity 平方时间复杂度
O(N^3): N cubic Complexity 立方时间复杂度
O(k^n): Exponential Growth 指数时间复杂度
O(N!): Factorial 阶乘时间复杂度
注意：只看最高复杂度的运算，并且不考虑前边的常数/系数
好的，上例菜！

• 不管n为多少，程序只执行一次，常数时间复杂度O(1)
  
• 不管n为多少，只执行3次，常数时间复杂度O(1)
• 代码执行n次，线性时间复杂度O(N)
  
• 代码执行N的平方次，平方时间复杂度O(N^2)
  
• 代码执行log2(n)次，对数时间复杂度O(log n)
  
• 斐波拉契数列使用了递归的形式，代码执行2的n次方次，指数时间复杂度O(k^n)
  
• 一个好的时间复杂度程序，会让程序跑起来更快更节省资源。最优的解决方案是运行最快，内存使用更少。用最简洁的时间和空间复杂度完成代码，基本上是一个顶尖职业选手的必备素养。
  

递归问题的情况分析

求 Fibonacci 数列的第 n 项
下面这段代码展开的话，要执行2的n次方次（n 为节点数），存在大量的代码冗余，时间复杂度为指数级别的O(2^N)。在面试中一定不要这样写，可以加一个缓存把中间结果缓存下来，或者直接用一个循环来写。

主定理

主定理用来解决所有递归函数，来计算它的时间复杂度。以下四种递归【二分法、二叉树、二维有序矩阵、归并排序】在面试和工程中比较常用，记住这四种情况就可以了。


答案：二叉树遍历、图的遍历和搜索算法的时间复杂度都是O(n)，n为节点数；二分查找的时间复杂度是O(log n)。

二、空间复杂度

两个原则

• 代码中有数组，那么数组长度基本上就是空间复杂度（如果是一维数组，数组长度n为传入元素的个数，则空间复杂度为O(n)；如果是二维数组，数组的长度为n的平方，则空间复杂度为O(n^2)。
• 代码中有递归，那么递归 最深的深度，就是空间复杂度的最大值。
• 如果又是递归，又开了数组，那两者之间的最大值就是我们的空间复杂度。

实战LeetCode的题目：ClimbingStairs

假设正在爬楼梯，需要 n 阶才能到达楼顶。每次可以爬1或2个台阶，请问有多少种不同的方法可以爬到楼顶？
1，1，2，3，5… 通项公式：F(n)=F(n-1)+F(n-2)
本质是求斐波那契数列的第 n 个值


本算法采用纯递归计算，没有任何缓存，也就是有大量的重复计算，每一层一分为二。




本算法增加了缓存数组，冗余部分不需要再重复计算，时间复杂度减小到了O(n)。但由于加了数组memo[ ]，数组长度为n+1，递归的最大深度是 n，所以空间复杂度是O(n)。



该算法，开了一维dp数组，数组长度是 n+1，递推深度为 n ，所以空间复杂度还是O(n)。其实递推的时候不需要存所有状态，只需要存 i-1 和 i-2 就行了。所以可以再次进行内存上的优化。

本算法不再申请数组，而是申请两个中间变量即可，再加一个第三变量就可以不断递推。在这里空间复杂度就变成了常数级O(1)。