14天阅读挑战赛
努力是为了不平庸~
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~
1. 题目描述
假设第1个月有1对初生的兔子，第2个月进入成熟期，第3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永不死去… .那么，由1对初生的兔子开始，12个月 后会有多少对兔子呢?
2.问题分析
不妨拿新出生的1对小兔子分析。
第1个月，小兔子①没有繁殖能力，所以还是1对。
第2个月，小兔子①进入成熟期，仍然是1对。
第3个月，兔子①生了1对小兔子②，于是这个月共有2 (1+1=2) 对兔子。
第4个月，兔子①又生了1对小兔子③，因此共有3 (1+2=3) 对兔子。
第5个月，兔子①又生了1对小兔子④，而在第3个月出生的兔子②也生下了1对小兔子⑤，因此共有5(2+3=5)对兔子。
第6个月，兔子①②③各生下了1对小兔子，新生的3对兔子加上原有的5对兔子，这个月共有8(3+5=8)对兔子。
。。。。。。
显然，前面相邻两项之和便构成后一项，即：当月的兔子数=上月兔子数+上上月的兔子数
斐波那契数列如下：
1,1,2,3,5,8,13,21,34,...
递归表达式：
F(n)={1,n=11,n=2F(n−1)+F(n−2),n＞2F(n)= \begin{cases} 1& \text{,n=1}\\ 1& \text{,n=2}\\ F(n-1)+F(n-2)& \text{,n＞2} \end{cases}F(n)=⎩⎨⎧11F(n−1)+F(n−2),n=1,n=2,n＞2
3.算法设计
//递归算法1int Fib(int n){if(n==1||n==2)return 1;return Fib(n-1)+Fib(n-2);}
4.算法分析
假设T(n)表示计算Fib(n)所需的基本操作次数，所以：
n=1时，T(n)=1;
n=2时，T(n)=1;
n=3时，T(n)=1+1+1=3;调用Fib(1)一次，Fib(2)一次，加法运算一次
即：n>2时，T(n)=T(n-1)+T(n-2)+1;
时间复杂度关系式：
T(n)={1,n=11,n=2T(n−1)+T(n−2)+1,n＞2T(n)= \begin{cases} 1& \text{,n=1}\\ 1& \text{,n=2}\\ T(n-1)+T(n-2)+1& \text{,n＞2} \end{cases}T(n)=⎩⎨⎧11T(n−1)+T(n−2)+1,n=1,n=2,n＞2
由此可知，T(n)≥F(n)
画出F(n)的递归树：
递归树的左侧从n每次递减1，直到2为止，左侧树高h1=n−1h_1=n-1h1=n−1
递归树的右侧从n每次递减2，直到2或1为止，右侧树高h2=n/2h_2=n/2h2=n/2
高度为h2h_2h2的部分是满二叉树，这部分节点数为2h2−12^{h_2}-12h2−1，即2n/2−12^{n/2}-12n/2−1，总节点数大于2n/22^{n/2}2n/2，每个节点都需要计算，时间复杂度是指数阶的。
图1 F(n)的递归树
∴T(n)是爆炸增量函数，时间复杂度太高，需要对算法进行改进！
5.算法改进
（1）斐波那契数列中的每一项(开头的两项除外)是前两项之和，如果记录前两项的值，则只需要一次加法运算就可以得到当前项的值，改进算法1如下：
//改进算法1int Fib2(int n){int *F=new int[n+1];//定义一个长度为n+1的数组，空间尚未使用F[1]=1;F[2]=1;for(int i=3;i<=n;i++)F[i]=F[i-1]+F[i-2];return F[n];}
很明显，改进算法1的时间复杂度为O(n)。由于使用了一个辅助数组记录中间结果，空间复杂度也为O(n)。
（2）其实只需要得到第n个斐波那契数，中间结果只是为了下一次使用，根本不需要记录。因此，可以采用迭代法进行算法设计，改进算法2如下：
//改进算法2int Fib3(int n){if(n==1||n-=2)return 1;int s1=1; //用s1和s2记录前面的两项int s2=1;for(int i=3;i<=n;i++){int tmp=s1+s2;s1=s2;s2=tmp; }return s2;}
改进算法2使用了几个辅助变量进行迭代，时间复杂度为O(n)，但空间复杂度降到了O(1)。
