斐波那契数列

[funnycoderstar]

JavaScript实现LeetCode第509题：斐波那契数列

斐波那契数列

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2：

输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.

示例 3：

输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.

 

提示：

0 ≤ N ≤ 30

1.暴力递归

/**
 * @param {number} N
 * @return {number}
 */
var fib = function(N) {
    // N小于等于1，则直接返回 N
    if (N <= 1) {
        return N;
    }
    // 通过递归关系调用自身
    return fib(N-1) + fib(N-2);
};

• 时间复杂度：O(2^n)。这是计算斐波那契数最慢的方法。因为它需要指数的时间。
• 空间复杂度：O(N)，在堆栈中我们需要与 N 成正比的空间大小。该堆栈跟踪 fib(N) 的函数调用，随着堆栈的不断增长如果没有足够的内存则会导致 栈溢出。

该方法存在大量重复的递归计算，例如 f(n) 和 f(n - 1) 两者向下递归需要 各自计算 f(n - 2) 的值。

2. 递归加缓存

原理： 在递归法的基础上，新建一个长度为 n 的数组，用于在递归时存储 f(0) 至 f(n) 的数字值，重复遇到某数字则直接从数组取用，避免了重复的递归计算。

/**
 * @param {number} N
 * @return {number}
 */
let cache = [0, 1];
function fib(N) {
    return typeof cache[N] === 'number' ? cache[N] : cache[N] = fib(N - 1) + fib(N - 2);
}

• 时间复杂度：O(N)。
• 空间复杂度：O(N)，使用了空间大小为 N 的数组。

3. 动态规划

使用 dp数组

/**
 * @param {number} N
 * @return {number}
 */
function fib(N) {
    const dp = [0, 1];
    for(let i = 2; i <= N; i++) {
        dp[i] = dp[i -1] + dp[i-2];
    }
    return dp[N];
}

• 时间复杂度：O(N)。
• 空间复杂度：O(N)，使用了空间大小为 N 的 dp 数组。

空间复杂度优化：

• 由于 dp 数组的第 i 项只与第 i−1 和第 i−2 项有关，因此只需要初始化三个变量 current, prev1, prev2 ，利用辅助变量 current 使 prev1, prev2 两数字交替前进即可
• 节省了 dp 数组的空间，因此空间复杂度降至 O(1) 。

/**
 * @param {number} N
 * @return {number}
 */
function fib(N) {
    // 若 N <= 1，则返回 N
    if (N <= 1) {
        return N;
    }
    // 若 N == 2，则返回 fib(2-1) + fib(2-2) = 1
    if (N == 2) {
        return 1;
    }
    // 至少需要三个变量存储 fib(N), fib(N-1) 和 fib(N-2)。
    let current = 0; // 代表 fib(N)
    let prev1 = 1; // 代表fib(N-1)
    let prev2 = 1; // 代表 fib(N-2)

    for (let i = 3; i <= N; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return current;
}

• 时间复杂度：O(N)。
• 空间复杂度：O(1)，仅仅使用了 current，prev1，prev2。

这是一道经典的面试题，笔者已经记不清楚有多少次面试中被问过这道题目了，其实想明白之后就会非常简单，要搞清楚为什么这三种方法，尤其是后两种比前一种做了哪些优化使其性能提升了。当然这道题有个限制 0 ≤ N ≤ 30 ，所以执行的时候，这三种方法的差异并不是很大，大家可以尝试一下比较大的数，就能体会到差异，真的是差很多。

参考

• leetcode题解