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

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

题目形容

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

解法 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];    }}

专注前台与算法的系列干货分享，欢迎关注(???)

image