【超直白】算法：斐波那契数列

admin管理员组

文章数量:1487745

【超直白】算法：斐波那契数列

题目：

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39

分析：

何为斐波那契额数列呢？？ 例如：0 1 1 2 3 5 8 13 说的通透些就是前两个数的和是后面那个数。 通项公式：F(n) = F(n-1)+F(n-2)

大家结合这张图和通式理一下思路，相信其实不难。就是一个简单的递归调用，最后调用到F(0)和F(1)截止。 代码如下所示：

代码语言：javascript代码运行次数：0运行复制

function test(n){
if(n==0){
return 0;
}else if(n==1){
return 1;
}else if(n>1){
var number  = test(n-1)+test(n-2);
return number  ;
}else{
return null;
}

}

这道题还没有完。因为由此可以看到这个算法的复杂度是2的N次方。（因为看图他每层都是以2的次幂进行增长的）所有他的时间复杂度极高。这个算法如果数极大的话是不合理的。 那么如何简化算法呢？ 提示：倒推运算，利用已得的结论去运算下一次的方法。

其实也很简单，就是利用比如前两个数相加的和等于第三个数，第四个数等于 第三个数据（也就是前两个数的和）加上前两个数中最大的那一个。按照此规律，即可优化本题算法。

代码语言：javascript代码运行次数：0运行复制

function testnew(n){
var a = 1;
var b = 0;
var num = null;
if(n>1){
for(let i=0;i<n-1;i++){
num = a+b;
b=a;
a= num;

}
return num;
}

}

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-12，如有侵权请联系 cloudcommunity@tencent 删除前往查看优化return递归数据算法

本文标签： 超直白算法斐波那契数列