一文学懂递归和动态规划( 二 ) _递归

这里大 O 表示的是一个算法在 worst case 的表现情况，这就是我们最关心的，不然春运抢车票的时候系统 hold 不住了，你跟我说这个算法很优秀？
当然还有其他衡量时间和空间的方式，比如
Theta: 描述的是 tight bound
<span style="color:blue">这也给我们了些许启发，不要说你平时表现有多好，没有意义；面试衡量的是你在 worst case 的水平；不要说面试没有发挥出你的真实水平，扎心的是那就是我们的真实水平。
那对于这个题来说，时间复杂度是多少呢？
答：因为我们每个节点都走了一遍，所以是把所有节点的时间加起来就是总的时间。
在这里，我们在每个节点上做的事情就是相加求和，是 O(1) 的操作，且每个节点的时间都是一样的，所以：
总时间 = 节点个数 * 每个节点的时间
那就变成了求节点个数的数学题：
在 N = 5 时，

文章插图

最上面一层有1个节点，
第二层 2 个，
第三层 4 个，
第四层 8 个，
第五层 16 个，如果填满的话，想象成一颗很大的树:)
这里就不要在意这个没填满的地方了，肯定是会有差这么几个 node，但是大 O 表达的时间复杂度我们刚说过了，求的是 worst case.
那么总的节点数就是：
1 + 2 + 4 + 8 + 16
这就是一个等比数列求和了，当然你可以用数学公式来算，但还有个小技巧可以帮助你快速计算：
<span style="color:blue"> 其实前面每一层的节点相加起来的个数都不会超过最后一层的节点的个数，总的节点数最多也就是最后一层节点数 * 2，然后在大 O 的时间复杂度里面常数项也是无所谓的，所以这个总的时间复杂度就是：
<span style="color:blue">
最后一层节点的个数：2^n
空间复杂度分析一般书上写的空间复杂度是指：
算法运行期间所需占用的所有内存空间
但是在公司里大家常用的，也是面试时问的指的是
Auxiliary space complexity ：
运行算法时所需占用的额外空间。
<span style="color:blue"> 举例说明区别：比如结果让你输出一个长度为 n 的数组，那么这 O(n) 的空间是不算在算法的空间复杂度里的，因为这个空间是跑不掉的，不是取决于你的算法的。
那空间复杂度怎么分析呢？
我们刚刚说到了冯诺伊曼体系，从图中也很容易看出来，是最左边这条路线占用 stack 的空间最多，一直不断的压栈，也就是从 5 到 4 到 3 到 2 一直压到 1，才到 base case 返回，每个节点占用的空间复杂度是 O(1)，所以加起来总的空间复杂度就是 O(n) .
我在上面:point_up_2:的视频里也提到了，不懂的同学往上翻看视频哦～
优化算法那我们就想了，为什么这么一个简简单单的运算竟然要指数级的时间复杂度？到底是为什么让时间如此之大。
那也不难看出来，在这棵 Recursion Tree 里，有太多的重复计算了。
比如一个 F(2) 在这里都被计算了 3 次，F(3) 被计算了 2 次，每次还都要再重新算，这不就是狗熊掰棒子吗，真的是一把辛酸泪。
那找到了原因之后，为了解决这种重复计算，计算机采用的方法其实和我们人类是一样的：记笔记。
对很多职业来说，比如医生、律师、以及我们工程师，为什么越老经验值钱？因为我们见得多积累的多，下次再遇到类似的问题时，能够很快的给出解决方案，哪怕一时解决不了，也避免了一些盲目的试错，我们会站在过去的高度不断进步，而不是每次都从零开始。
回到优化算法上来，那计算机如何记笔记呢？
我们要想求 F(n)，无非也就是要
记录 F(0) ~ F(n-1) 的值，
那选取一个合适的数据结构来存储就好了。
那这里很明显了，用一个数组来存：
Index012345F(n)011235
那有了这个 cheat sheet，我们就可以从前到后得到结果了，这样每一个点就只算了一遍，用一个 for loop 就可以写出来，代码也非常简单。

class Solution {public int fib(int N) {if (N == 0) {return 0;}if (N== 1) {return 1;}int[] notes = new int[N+1];notes[0] = 0;notes[1] = 1;for(int i = 2; i <= N; i++) {notes[i] = notes[i-1] + notes[i-2];}return notes[N];}}

这个速度就是 100% 了～