题目： 计算斐波那契数列第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);
}
针对递归方法的教学，斐波那数列可能是最常用来拿来举例的了，但是，实际计算时绝不推荐使用递归方法，很容易stack overflow。可以在浏览器中计算个fibonacci(100)试试。而且其时间复杂度为指数级，可以近似认为是2^n, 当然准确点可能是1.6^n。
其时间复杂度的计算： 递推关系式为f(n)=f(n-1)+f(n-2)；显然是一个2阶常系数查分方程，其特征方程为x^2-x-1=0。 得其解x， 时间复杂度为O(1.618^n)
或者另一种思路： 该方法的递归求解过程其实就是其二叉树展开的过程，时间复杂度就是计算该二叉树的节点个数： 树高n层， 但不是满二叉树，忽略常数，是O(2^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]])； 根据初始的几个值，带入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次方的问题。
首先考虑如何很快的计算一个整数的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，所以其对应的值相乘即是结果)
所以在计算一个整数的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进制表示的长度。加法的时间复杂度为常数，而计算乘法的次数为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
类似菲波那切数列。
扩展2： 变态跳台阶
一只青蛙一次可以跳上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)
分析前面几个例子，找规律：
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);
...
发现 n>=2时都满足，f(n) = 2f(n-1); 所以此时f(n) = f(1) * 2^(n-1) = pow(2, n-1);
