您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

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

时间:03-08来源:作者:点击数:

题目:

大家都知道斐波那契数列,现在要求输入一个整数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)截止。

代码如下所示:

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的次幂进行增长的)所有他的时间复杂度极高。这个算法如果数极大的话是不合理的。

那么如何简化算法呢?

提示:倒推运算,利用已得的结论去运算下一次的方法。

在这里插入图片描述

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

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;
}

}
方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门