斐波那契数，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
