js实现斐波那契的三种算法

斐波那契数，f(n) = f(n-1) + f(n-2);
例：
1 2 3 4 5 6 7
1 1 2 3 5 8 13
废话少说，首先来个最简单的，复杂度也是最大的

//复杂度为2的n次方
var fib = function(n){
    if(n == 1 || n == 2){
        return 1;
    }
    return (fib(n-1)+fib(n-2));
};

再来个复杂度为 n 的，

//高级一点的斐波那契，其实就是多个‘缓存’，复杂度为 n
var smartFib = (function(){
    var fibsequence = [0,1,1];//用数组来存储已经计算过的值
    var fib = function(n){
        if(fibsequence[n]){
            return fibsequence[n];
        }
        fibsequence[n] = fib(n-1)+fib(n-2);
        return fibsequence[n];
    }
    return {'fib':fib,'fibsequence':fibsequence};
})();

最后也是最流弊的,当然，得先贴个公式（看不懂那就得回去复习线性代数课本啦）：

Paste_Image.png

//更高级的斐波那契 复杂度为logn;
var yuan = [[1,1],[1,0]];//元数据
//矩阵相乘
var matrixMultiply = function(a,b){
   var c = [[0,0],[0,0]];
   c[0][0] = a[0][0]*b[0][0]+a[0][1]*b[1][0];
   c[0][1] = a[0][0]*b[0][1]+a[0][1]*b[1][1];
   c[1][0] = a[1][0]*b[0][0]+a[1][1]*b[1][0];
   c[1][1] = a[1][0]*b[0][1]+a[1][1]*b[1][1];
   return c;
};
//缓存已经计算过了的结果，避免重复计算，与第二个思路一样，不过存储的是矩阵
var sequence = [0,[[1,1],[1,0]]];
var nbFib = function(n){
//这里的n是公式里的n-2,看最后的调用就知道了。
    if(n<1){
        return [[0,1],[]];//本来return 1 就行了，但是后面得到结果的时候有个sum[0][0]+sum[0][1],为了方便而已，不用管它;
    }
    if(n == 1){
        return yuan;//二分到最底层了
    }
    if(sequence[n]){
        return sequence[n];//如果计算过了就直接从数组里面拿过来用，
    }else{
        if(n%2 == 0){
            sequence[n] = matrixMultiply(nbFib(n/2),nbFib(n/2))
            return sequence[n];
        }else{
            var temp = matrixMultiply(nbFib((n-1)/2),nbFib((n-1)/2));
            sequence[n] = matrixMultiply(yuan,temp);//把漏掉的那个给补上
            return sequence[n];
        }
    }
}

调用

var n = 40;

console.time('n:');
console.log(smartFib.fib(n));//102334155
console.timeEnd('n:');//耗时 2ms

console.time('logN:');
var sum = nbFib(n-2);//这里是n-2，为什么是n-2看公式啦;
console.log(sum[0][0]+sum[0][1]);//102334155，不要问我为啥f(n)=sum[0][1]+sum[0][1];
console.timeEnd('logN:');//耗时 1ms

console.time('2的n次方:');
console.log(fib(n));//102334155
console.timeEnd('2的n次方:');//耗时 938ms