斐波那契數(shù)捡需，f(n) = f(n-1) + f(n-2);
例：
1 2 3 4 5 6 7
1 1 2 3 5 8 13
廢話少說，首先來個最簡單的唠亚，復(fù)雜度也是最大的
//復(fù)雜度為2的n次方
var fib = function(n){
if(n == 1 || n == 2){
return 1;
}
return (fib(n-1)+fib(n-2));
};
再來個復(fù)雜度為 n 的区丑，
//高級一點(diǎn)的斐波那契，其實(shí)就是多個‘緩存’橱野，復(fù)雜度為 n
var smartFib = (function(){
var fibsequence = [0,1,1];//用數(shù)組來存儲已經(jīng)計算過的值
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};
})();
最后也是最流弊的,當(dāng)然朽缴，得先貼個公式（看不懂那就得回去復(fù)習(xí)線性代數(shù)課本啦）：
Paste_Image.png
//更高級的斐波那契 復(fù)雜度為logn;
var yuan = [[1,1],[1,0]];//元數(shù)據(jù)
//矩陣相乘
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;
};
//緩存已經(jīng)計算過了的結(jié)果，避免重復(fù)計算水援，與第二個思路一樣密强，不過存儲的是矩陣
var sequence = [0,[[1,1],[1,0]]];
var nbFib = function(n){
//這里的n是公式里的n-2,看最后的調(diào)用就知道了。
if(n<1){
return [[0,1],[]];//本來return 1 就行了裹唆，但是后面得到結(jié)果的時候有個sum[0][0]+sum[0][1],為了方便而已誓斥，不用管它;
}
if(n == 1){
return yuan;//二分到最底層了
}
if(sequence[n]){
return sequence[n];//如果計算過了就直接從數(shù)組里面拿過來用，
}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);//把漏掉的那個給補(bǔ)上
return sequence[n];
}
}
}
調(diào)用
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
