剑指offer - 斐波那契数列 - JavaScript

【2种解法】【JavaScript系列题解】【斐波那契数列】

题目描述

大家都知道斐波那契数列，现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0）。n<=39。

专注前端与算法的系列干货分享，欢迎关注(¬‿¬)：
「微信公众号：心谭博客」| xxoo521.com | GitHub

解法 1: 数学定义

根据数学定义：f(n) = f(n - 1) + f(n - 2)。最初始情况是f(0) = 0和f(1) = 1。

因此直接循环更新即可。时间复杂度 O(N)，空间复杂度 O(1)。

// 原文地址：https://xxoo521.com/2019-12-25-fei-bo-na-qi/
// ac地址：https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3

/**
 * @param {number} n
 * @return {number}
 */
function Fibonacci(n) {
    if (n === 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }

    let a = 0,
        b = 1;
    for (let i = 2; i < n; ++i) {
        let c = a + b;
        a = b;
        b = c;
    }

    return a + b;
}

解法 2: 递归 + 动态规划

根据数学定义：f(n) = f(n - 1) + f(n - 2)，代码可以实现为递归形式。

但是以 f(5)为例，它的过程如下：

1. f(5) = f(4) + f(3)
2. f(4) = f(3) + f(2)
3. f(3) = f(2) + f(1)
4. ...省略

注意在第 2 步和第 3 步中，我们计算了 2 次 f(3)的值。当要求的 n 越大的时候，重复计算就会越多，时间复杂度就会越高。

在动态规划的一种做法中，可以借助“备忘录”来实现结果的缓存，避免重复计算。

代码如下，时间复杂度是 O(N)，空间复杂度是 O(1)。

// 原文地址：https://xxoo521.com/2019-12-25-fei-bo-na-qi/
// ac地址：https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3

/**
 * @param {number} n
 * @return {number}
 */
function Fibonacci(n) {
    const cache = {
        0: 0,
        1: 1
    };
    return __Fibonacci(n);

    /**
     * @param {number} n
     * @return {number}
     */
    function __Fibonacci(n) {
        if (cache[n] !== undefined) {
            return cache[n];
        }

        cache[n] = __Fibonacci(n - 1) + __Fibonacci(n - 2);
        return cache[n];
    }
}

“备忘录”的其他优点

虽然备忘录用了 O(N)的空间。但是重复计算同个 f(n)的结果时候，时间复杂度是 O(1)。比如之前调用过一次Fibonacci(10)，那么 f(10)的结果就缓存在了 cache 中。再次调用函数，直接从缓存读取即可。

同样地，当 n < 10 时候，结果都是从 cache 中直接读取，时间复杂度均是 O(1)。

再推广，当计算 f(20)的时候，n < 10 的结果都计算完了，不需要重复计算。效率是高于第一种循环写法的调用。

总结：备忘录缓存了计算结果，避免了多次调用时的重复计算。