斐波那契数列的多种解法

前言

求任意位置的斐波那契数，最常见的做法是使用递归，这种做法虽然可以得到结果，但是它的性能很差。

本文跟大家分享一种性能较好的解决方案，欢迎各位感兴趣的开发者阅读本文。

概念

我们先来看下什么是斐波那契数列，有一个数列它的0号位置的值是0，1号位置的值是1，当要求的位置(n)大于1时，其值为(n-1)+(n-2)。

我们举个例子来说明下：

我们要求5号位置的斐波那契数，那么我们就要求出5-1位置的斐波那契数和5-2位置的斐波那契数。

• 4号位置的斐波那契数为 f(4-1) + f(4-2)
• 3号位置的斐波那契数为 f(3-1) + f(3-2)
• 2号位置的斐波那契数为 f(2-1) + f(2-2)
• 1号位置的斐波那契数为 1
• 0号位置的斐波那契数为 0

如上所示，我们想知道5号位置的斐波那契数就得先知道4号和3号位置的斐波那契数，以此类推直到1号位置和0号位置，那么：

• 2号位置的斐波那契数就为：1 + 0 = 1
• 3号位置的斐波那契数就为：1 + 1 = 2
• 4号位置的斐波那契数就为：2 + 1 = 3
• 5号位置的斐波那契数就为：3 + 2 = 5

解决方案

接下来，我们来详细讲解下这这个问题的解决方案。

递归解决

很多教材在讲解递归时，都会使用求斐波那契数作为例子，因此许多开发者在看到这道题的时候，一下子就能想到这道题应该用递归来解。

在我的另一篇文章：递归的理解与实现 中详细讲解了斐波那契数列的递归解法。此处不做过多阐述，只画一下上述例子的递归树，如下所示：

image-20210623225441611.png

观察上述递归树，我们会发现有好多节点都是重复的，而且重复的节点数会随着n的增大而急剧增加，也意味着计算量会随着n的增大而急剧增大，因此它的性能是非常差的。

自下而上

上述代码之所以慢，是因为重复的计算太多了，我们可以采用从下往上计算的方式，首先根据f(0)和f(1)算出f(2)，再根据f(1)和f(2)算出f(3)，以此类推就可以算出第n项了，它的时间复杂度是O(n)，我们把这种解法称为自下而上。

我们画个图来讲解下上述思路：

image-20210624004744829.png

实现代码

我们分析完上述思路后，接下来就可以将其转换为代码了，如下所示：

export default class Fibonacci {
  private readonly index: number;
  constructor(index: number) {
    this.index = index;
  }
  
  /**
   * 自下往上实现
   * 实现思路：
   *   1. 根据f(0)和f(1)算出f(2)
   *   2. 再根据f(1)和F(2)算出f(3)
   *   3. 以此类推算出第n项
   * 时间复杂度分析：它从第0项遍历到最后一项，因此时间复杂度为O(n)
  */
  public bottomUp(): number {
    const result: Array<number> = [0, 1];
    if (this.index < 2) {
      return result[this.index];
    }

    // f(n - 1)
    let fibNMinusOne = 1;
    // f(n - 2)
    let fibNMinusTwo = 0;
    let fibN = 0;
    for (let i = 2; i <= this.index; ++i) {
      // f(n) = f(n - 1) + f(n - 2)
      fibN = fibNMinusOne + fibNMinusTwo;

      // f(n - 2) = f(n - 1)
      fibNMinusTwo = fibNMinusOne;
      // f(n - 1) = f(n)
      fibNMinusOne = fibN;
    }
    return fibN;
  }
}

我们写个测试用例来执行下上述代码，检查下正确性，如下所示，我们需要求斐波那契数列的第100号位置的值：

import Fibonacci from "../Fibonacci.ts";

const fibonacciTest = new Fibonacci(100);
console.log("斐波那契数列的第1000号位置的值为：", fibonacciTest.bottomUp());

运行结果如下所示：

image-20210624010227349.png

完整代码请移步：Fibonacci.ts

写在最后

至此，文章就分享完毕了。

我是神奇的程序员，一位前端开发工程师。