JavaScript 斐波那契数列问题

最近不忙，准备巩固一下基本功，看了点算法的东西。这里记录一下斐波那契数列算法，及其对于时间复杂度的优化方法。

关于斐波那契数列，传送门在此。
就是这样的数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55......
从第三项开始，每一项等于前两项之和，不多BB，往下看

一、递归（最容易想到的方法）

这个数列的第 0 项我们一般看作是 0，即：

代码实现如下(只考虑 n 是自然数的情况):

function Fibonacci(n) {
    if (n <= 1 ) {
        return n;
    } else {
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

虽说能正确计算，但是其仅在 n <= 1 时，时间复杂度为 O(1)
当 n >= 2 时

         F(5)   
        /     \     
    F(3)       F(4)   
    /   \      /   \
F(1)   F(2)    F(2)  F(3)
      /   \   /  \   /  \

通过这个树，我们能看出它的时间复杂度是 O(2^n)

话说大学时候，学校的 OJ 上做过这题，当时就是用的递归，AC 以后就没再继续深入研究过

二、利用数组（可将时间复杂度优化为 O(n) ）

function Fibonacci(n) {
    if (n <= 1 ) {
        return n;
    } else {
        var arr = [];
        arr[0] = 0;
        arr[1] = 1;

        for (var i = 2; i <= n; i ++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n]
    }
}

也是挺巧妙的一种方法，不过需要创建数组，占用了一定的内存空间，虽说现在的手机、电脑也不差这点内存，但是还是可以优化一下

三、利用中间变量（时间复杂度也是 O(n)，但可以节省空间）

同方法二思想类似，不过不使用数组

function Fibonacci(n) {
    if (n <= 1 ) {
        return n;
    } else {
        var temp0 = 0;
        var temp1 = 1;
        var fn = 0;

        for (var i = 2; i <= n; i ++) {
            fn = temp0 + temp1;
            temp0 = temp1;
            temp1 = fn;
        }
        return fn
    }
}

变量位置互换的思想

四、利用矩阵（可将时间复杂度优化为 O(log n) ）

这个就属于用空间换时间了

话说这个矩阵我好像还给了大学老师，等我看会了再写上来，尴尬

五、高中数学（ O(1) ）

这个就是高中数学知识了，构造等比数列，求通项

话说这个好像也还给高中老师了，好在高中数学还不错，捡了回来

鹏哥带你们复习一下高中数学：

已知等比数列：1, 3, 9, 27, 81...... 求其第 n 项
很显然公比为 3，直接套公式，a(n) = a(1) * q^(n - 1)
即 a(n) = 3^(n - 1)

话说这个 markdown 写数学公式是真难受啊

然后在看这个斐波那契数列，看起来不是等比，这就需要我们去构造等比，眼前浮现出高中数学老师粉笔一挥，抑扬顿挫的说差后成等比的情景，怀念啊……

推导过程有点长，有空我整理下再发上来，先看通项

通项公式

function Fibonacci(n) {

    var sqrt5 = Math.sqrt(5);
    var ratio = 1 / sqrt5;
    var base1 = (sqrt5 + 1) / 2;
    var base2 = (1 - sqrt5) / 2;
    var fn = ratio * (Math.pow(base1, n) + (Math.pow(base2, n)));
    
    return Math.round(fn);
}

不过这个，浮点数你懂的，精度上要差一些。
这里只是做以讨论，没有考虑浮点数加减乘除的问题，n <= 75 时是正确的，n = 76 时就开始有偏差了，关于浮点数运算问题有空再写吧

根据情况选择对应的方法吧，数值越大，矩阵运算的时间优势体现越明显