剑指offer__9:计算斐波那契数列的3种方法及复杂度分析

题目： 计算斐波那契数列第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 = (2¹⁾2, 2^4 = (2²⁾2, 2^8 = (2⁴⁾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);