PHP算法之斐波那契数列(递归)

/*斐波那契数列 源代码分析

f(x) =  1 ;            当 x < 2 ;

f(x) = f(x-1)+f(x-2);  当 x >= 2 ;

通项式为:fn ={((1+根号5)/2)^n-((1-根号5)/2)^n}/(根号5)

则根据通项式构造函数求fn;

*/

//计时函数  console.time() //计时开始  console.timeEnd() //计时结束并输出时长

console.time();

var i;

var total;

//方法一  使用原始方法

function fibo(i)

{

    if(i == 0){

        return 1;

    }else if(i == 1){

        return 1;

    }else{

        total = fibo(i-1) + fibo(i-2);

        return total;

    }

}

//方法二 使用迭代解法, 将每一次执行的数据保存起来,时间会大大缩短

function  fibo1(i)

{

    if(i<=1){

        return 1;

    }

    var pre = 1;

    var prepre = 1;

    for(j = 2; j <= i; j++){

        total = pre + prepre;

        prepre = pre;

        pre = total;

    }

    return total;

}

console.log(fibo(40));//结果为:165580141  时间为:2313.9990234375ms;

console.log(fibo1(40));//结果为:165580141  时间为:0.805908203125ms;

console.timeEnd();

对比结果可能fibo1函数明显比fibo函数优化的明显,时间复杂度为O(x);

fibo1的思路为:将每一次递归的数值保存起来,后期就不需要再次的寻找;

关于斐波那契数列优化的方法还有很多,这里先将这一种,还有一些涉及到比较难懂的高等数学,对于初学者会比较的难学;

注意:上述代码为js代码,请嵌入到html文件中运行;

计时函数 console.time() //计时开始

console.timeEnd() //计时结束并输出时长

单位以ms来计算;