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

题目：

大家都知道斐波那契数列，现在要求输入一个整数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;
}

}