递归算法和非递归算法求解斐波那契数列并计算时间复杂度

首先了解线性递推数列的特征方程

（1）数列的特征方程：

假设一个数列：Xn+2 = C1Xn+1 + C2Xn

设有r,s使Xn+2 - rXn+1 = S(Xn+2-rXn);

所以Xn+2 = (s+r)Xn+1 - srXn;

得到 C1 = s+r;C2 = -sr;

消去s得到特征方程式：r^2 = C1*r + C2;

（2）使用二阶递推求斐波那契数列。

斐波那契数列：

F(n)=1, n=0,1;

F(n)=F(n-1) + F(n-2), n >1;

当n>1时进行r和s的求解得到r^2 = r + 1;

即x^2 = x + 1;

解得p = （1+√5）/2，q = （1-√5）/2；

则Xn = (1/√5)[（1+√5）/2)^n-(（1-√5）/2)^n]

（3）代码部分

递归代码：

int F(int n){

if(n <=1){

return 1;

}

return F(n-1) + F(n-2);

}

得到T(n)= O((1/√5)[（1+√5）/2)^n-(（1-√5）/2)^n])

非递归代码：

int F(int n){

if(n<=1)return 1;

int first = 1;

int second = 1;

int end= 0;

int i = 2;

while(i <= n ){

end= first + second;

first = second;

second = end;

i++;

}

return end;

}时间复杂度为O(n)

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/Warmth_Dream/article/details/81612096
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-03-07 18:00:05
阅读 ( 1299 )
分类：算法

递归算法和非递归算法求解斐波那契数列并计算时间复杂度

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看