題目： 計算斐波那契數(shù)列第n項的值
n = 0, f(0) = 0;
n = 1, f(1) = 1;
n >= 2, f(n) = f(n-1) + f(n-2);
遞歸方法（not recommend）
function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n-1) + fibonacci(n-2);
}
針對遞歸方法的教學甚负，斐波那數(shù)列可能是最常用來拿來舉例的了贰逾，但是，實際計算時絕不推薦使用遞歸方法映穗，很容易stack overflow恶阴》直穑可以在瀏覽器中計算個fibonacci(100)試試。而且其時間復雜度為指數(shù)級存淫，可以近似認為是2^n, 當然準確點可能是1.6^n。
其時間復雜度的計算： 遞推關系式為f(n)=f(n-1)+f(n-2)沼填；顯然是一個2階常系數(shù)查分方程桅咆，其特征方程為x^2-x-1=0。 得其解x坞笙， 時間復雜度為O(1.618^n)
或者另一種思路： 該方法的遞歸求解過程其實就是其二叉樹展開的過程岩饼，時間復雜度就是計算該二叉樹的節(jié)點個數(shù)： 樹高n層， 但不是滿二叉樹薛夜，忽略常數(shù)籍茧，是O(2^n)
將遞歸展開，以循環(huán)方式計算
function fibonacci(n) {
if (n <= 1) {
return n;
}
let one = 0;
let two = 1;
let res;
for (let i = 2; i <= n; i++){
res = one + two;
one = two;
two = res;
}
return res;
}
事件復雜度為O(n)
轉化為二階矩陣的階乘方程
f(n) = f(n-1) + f(n-2)是一個二階差分方程梯澜，一定可以轉化為矩陣乘法的形式（寞冯？）： (f(n), f(n-1)) = (f(n-1), f(n-2)·[[a, b], [c, d]])； 根據(jù)初始的幾個值，帶入n=2,n=3的結果可得吮龄，a=b=c=1, d=0;
所以(f(n), f(n-1)) = (f(2), f(1))·[[1, 1], [1, 0]]^(n-2)俭茧。所以問題已經轉化成了如何最快計算一個矩陣的n次方的問題。
首先考慮如何很快的計算一個整數(shù)的n次方漓帚？
比如2的9次方：
- 9的2進制表示為 1001（長度為4）
- 2^9 = 2^1 * 2^8 （中間計算4次： 2^1, 2^2 = (21)2, 2^4 = (22)2, 2^8 = (24)2母债， 因為只有第1、4對應位置是1尝抖，所以其對應的值相乘即是結果)
所以在計算一個整數(shù)的N次方時毡们，需要計算logN（其二進制的長度）次，即事件復雜度為O(logN)
function pow(base, power) {
let b = base;
let res = 1;
while (power) {
// 2進制中當前位置不為0
if ((power & 1) !== 0) {
res *= b;
}
// 2進制不斷右移
power >>= 1;
// 得到當前位置所對應的基準值
b *= b;
}
return res;
}
如何計算矩陣的N次方昧辽？
C=[[1, 1], [1, 0]]; 求C^N:
const C = [[1, 1], [1, 0]];
//計算2階矩陣的乘積
function matricsMultiple (C1, C2) {
const [a1, b1] = C1[0];
const [c1, d1] = C1[1];
const [a2, b2] = C2[0];
const [c2, d2] = C2[1];
return [
[a1 * a2 + b1 * c2, a1 * b2 + b1 * d2],
[c1 * a2 + d1 * c2, c1 * b2 + d1 * d2]
];
}
function matricsPow (C, power) {
let res = [[1, 0], [0, 1]];
let b = C;
while (power) {
if ((power & 1) !== 0) {
res = matricsMultiple(res, b);
}
power >>= 1;
b = matricsMultiple(b, b);
}
return res;
}
回歸正題
關系式： (f(n), f(n-1)) = (f(2), f(1))·[[1, 1], [1, 0]]^(n-2) = （1, 1)·[[1, 1], [1, 0]]^(n-2)
令 [[a, b], [c, d]] 為 [[1, 1], [1, 0]]^(n-2)的解衙熔，則const [[a, b], [c, d]] = matricsPow(C, n-2)；又有
(1, 1) · [[a, b], [c, d]] = (a+c, b+d)奴迅， 所以fn = a+c青责；
最終算法為：
function fibonacci (n) {
if (n <= 1) {
return n;
}
if (n === 2) {
return 1;
}
// 計算矩陣的平方
function matricsMultiple (C1, C2) {
const [a1, b1] = C1[0];
const [c1, d1] = C1[1];
const [a2, b2] = C2[0];
const [c2, d2] = C2[1];
return [
[a1 * a2 + b1 * c2, a1 * b2 + b1 * d2],
[c1 * a2 + d1 * c2, c1 * b2 + d1 * d2]
];
}
function matricsPow (C, power) {
let res = [[1, 0], [0, 1]];
let b = C;
while (power) {
if ((power & 1) !== 0) {
res = matricsMultiple(res, b);
}
power >>= 1;
b = matricsMultiple(b, b);
}
return res;
}
const C = [[1, 1], [1, 0]];
const [[a, _b], [c, _d]] = matricsPow(C, n - 2);
return a + c;
}
時間復雜度為O(logN)，及N的2進制表示的長度取具。加法的時間復雜度為常數(shù)脖隶，而計算乘法的次數(shù)為logN，所以得時間復雜度為O(logN)
擴展1： 跳臺階問題
一只青蛙一次可以跳上1級臺階暇检，也可以跳上2級产阱。求該青蛙跳上一個n級的臺階總共有多少種跳法。
找關系： 第一次有兩種選擇：跳1級块仆，還剩n-1個臺階构蹬； 跳2級，還剩n-2個臺階
f(n) = f(n-1) + f(n-2), f(1) = 1, f(2) = 2
類似菲波那切數(shù)列悔据。
擴展2： 變態(tài)跳臺階
一只青蛙一次可以跳上1級臺階庄敛，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法科汗。
f(n) = f(n-1) + f(n-2) + f(n-3) + ... +f(n-n) = f(0) + f(1) + ... + f(n-1)
分析前面幾個例子藻烤，找規(guī)律：
f(1) = 1;
f(2) = f(2-1) + f(2-2) = f(0) + f(1) = 2;
f(3) = f(3-1) + f(3-2) + f(3-3) = f(0) + f(1) + f(2) = 2f(2);
f(4) = f(4-1) + f(4-2) + f(4-3) + f(4-4) = f(0) + f(1) + f(2) + f(3) = 2f(3);
...
發(fā)現(xiàn) n>=2時都滿足，f(n) = 2f(n-1); 所以此時f(n) = f(1) * 2^(n-1) = pow(2, n-1);
