递归、斐波那契数列
异步社区
假设第一个月有一对初生的兔子,第2个月进入成熟期,第三个月进行生育兔子,而一对成熟的 兔子每月会生1对兔子,兔子永不死去,那么从第一对初生的兔子开始,12个月后会有多少只兔子?
不妨拿新出生的1对小兔子分析。 第1个月,小兔子①没有没有繁殖能力,所以还是1对 第2个月,小兔子①进入成熟期,所以还是1对 第3个月,兔子①生了一对兔子②,于是共有2对兔子 第4个月,兔子①生了一对兔子③,共有3对兔子 … 以此类推
这个数列有十分明显的特点:从第三个月开始, 当月的兔子数量 = 上月兔子数 + 当月新生兔子 当月新生兔子 = 上上个月的兔子 因此,前面相邻两项之和,便构成了后一项,换言之 当月兔子数 = 上月兔子数 + 上上月兔子数 斐波那契数列如下: 1,1,2,3,5,8,13,21,34,… 递归表达式如下:
int Fib1(int n){
if(n==1||n==2)
return 1;
return Fib1(n-1)+Fib1(n-2);
}
上面的代码是否正确? 算法复杂度如何? 算法是否能改进?
1、首先公式是推导出来的,算法正确性肯定没问题 2、那么复杂度呢 假设T(n) 表示计算Fib1(n)所需的基本操作次数,那么
n=1时,T(n)=1;
n=2时,T(n)=1;
n=3时,T(n)=3;//调用Fib1(2)和Fib1(1)并执行一次加法运算(Fib1(2)+Fib1(1))
因此,当n>2时候,
T(n)=T(n-1)+T(n-2)+1;
递归表达式 和时间复杂度T(n)的关系如下:
由此可得,T(n)>=F(n) 那么如何计算F(n)呢? 其中一种,就是画出F(n)的递归树,可以看出,时间复杂度是指数阶级的。
另一种是求斐波那契数列的通项公式:
算法改进: 斐波那契数列中的每一项(开头的两项除外)是前两项之和,如果记录前两项的值,则只需要一次加法运算就可以得到当前项的值,时间复杂度会不会降低一些呢?不妨用数组看看
int 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];
}
很明显,时间复杂度为O(n),因为使用了辅助数组,所以空间复杂度也是O(n)。算法复杂度大大降低。
还可以使用迭代法来取消空间复杂度。
int 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;
}
这样空间复杂度就降到了O(1)。那还不能再降低呢?实际上还可以降低到O(logn),对数阶。