题目描述

[EN | CN]

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

1
2
tF(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 N,计算 F(N)

示例 1:

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

示例 2:

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

示例 3:

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

提示:

0 ≤ N ≤ 30

解法 1:普通递归

简单粗暴根据定义来递归,但是因为存在很多冗余运算,所以效率比较低。

假设数列长度为 $n$,那么

  • 时间复杂度为 $O(1.618^n)$,如果仔细观察计算量随 $n$ 的增大的变化,会发现其计算量也相当于一个斐波那契数列(略有差别),而斐波那契数列的前后两项之比组成的序列会趋近于黄金分割等比数列(见 维基百科),因此该解法的时间复杂度为指数级,底数为 1.618;
  • 空间复杂度为 $O(n)$,递归的栈深最大为 $n$。

实现与结果如下:

1
2
3
4
5
class Solution:
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        return self.fib(N - 1) + self.fib(N - 2)
  • Runtime: 1028 ms, faster than 24.47% of Python3 online submissions for Fibonacci Number.
  • Memory Usage: 12.6 MB, less than 100.00% of Python3 online submissions for Fibonacci Number.

解法 2:普通迭代(动规)

既然普通递归会产生很多重复的运算,而这些运算其实可以在计算过程的中间保存起来,避免再次运算,因此我们可以用迭代方法来实现,从 0 迭代到 N。并且由于对于该数列的某个数而言,只需要斐波那契数列中相邻的前两个数,因此在迭代的过程中我们只需要保存两个值(当前值和前一个值)即可。

假设数列长度为 $n$,那么

  • 时间复杂度为 $O(n)$,从头到尾计算一遍;
  • 空间复杂度为 $O(1)$。

实现与结果如下:

1
2
3
4
5
6
7
8
class Solution:
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        x1, x2 = 0, 1
        for _ in range(1, N):
            x1, x2 = x2, x1 + x2
        return x2
  • Runtime: 20 ms, faster than 99.94% of Python3 online submissions for Fibonacci Number.
  • Memory Usage: 12.6 MB, less than 100.00% of Python3 online submissions for Fibonacci Number.

解法 3:尾递归

其实解法 1 的普通递归存在着很大的优化空间,比如说:

  • 可以改成动态规划,避免重复的运算;
  • 可以改成尾递归,通过编译器来优化递归的函数调用栈。

这里我们要了解一下 尾递归的概念

在计算机学里,尾调用 是指一个函数里的最后一个动作是返回一个函数的调用结果的情形,即最后一步新调用的返回值直接被当前函数的返回结果。此时,该尾部调用位置被称为 尾位置。尾调用中有一种重要而特殊的情形叫做 尾递归。经过适当处理,尾递归形式的函数的运行效率可以被极大地优化。尾调用原则上都可以通过简化函数调用栈的结构而获得性能优化(称为“尾调用消除”),但是优化尾调用是否方便可行取决于运行环境对此类优化的支持程度如何。

那么我们的思路就转为如何将斐波那契数列函数转为一个「返回一个函数调用结果的函数」,并且要用到之前计算过的结果。为此我们可以引入一个 helper 函数,然后该 helper 函数接受斐波那契数列中的前两个数 x1x2,并且还有另一个参数 steps 来指示还需要计算多少步。这样一来,我们就可以在最后返回 helper 函数的调用结果,实现尾调用。

假设数列长度为 $n$,那么

  • 时间复杂度为 $O(n)$,从头到尾计算一遍;
  • 空间复杂度为 $O(1)$,尾递归将调用栈消除了,不需要额外空间;注意如果编译器不支持尾递归优化,那么该解法的空间复杂度还是 $O(n)$。

实现与结果如下:

1
2
3
4
5
6
7
8
9
class Solution:
    def fib(self, N: int) -> int:
        def fib_(x1, x2, steps):
            if steps < 2:
                return steps
            if steps == 2:
                return x1 + x2
            return fib_(x2, x1 + x2, steps - 1)
        return fib_(0, 1, N)
  • Runtime: 32 ms, faster than 90.98% of Python3 online submissions for Fibonacci Number.
  • Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for Fibonacci Number.

解法 4:通项公式法

斐波那契数列是一个很有规则的数列,因此我们可以尝试推导其通项公式,如果能得到通项公式,就能一步到位地计算。

已知斐波那契数列的一般形式为 $x_n = x_{n - 1} + x_{n - 2}$,假设我们能找到两个数 $a$、$b$ 使得 $x_n - a x_{n - 1} = b(x_{n - 1} - a x_{n - 2})$(公式 1),那么我们移项得到 $x_n = (a + b) x_{n - 1} + (-ab) x_{n - 2}$,即 $\begin{cases} a + b = 1 \\ ab = -1 \end{cases}$,解二元一次方程得到 $\begin{cases} a = \frac{1 + \sqrt{5}}{2} \\ b = \frac{1 - \sqrt{5}}{2} \end{cases}$($a$、$b$ 可互换)。

然后我们再将其代入到公式 1,得到

$$ \begin{aligned} x_n - a x_{n - 1} &= b (x_{n - 1} - a x_{n - 2}) \\ &= b^{n - 1} (x_1 - a x_0) \\ &= b^{n - 1} \\ \end{aligned} $$

又因为我们已知 $a$、$b$ 的解并且 $a$、$b$ 可互换,我们代入上式可以得到

$$ \begin{cases} x_n - a x_{n - 1} &= b^{n - 1} \\ x_n - b x_{n - 1} &= a^{n - 1} \\ \end{cases} $$

解得

$$ x_n = \frac{a^n - b^n}{a - b} $$

代入 $a$、$b$ 的具体值,得到通项公式

$$ x_n = \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^2 - (\frac{1 - \sqrt{5}}{2})^2] $$

假设数列长度为 $n$,那么

  • 时间复杂度为 $O(n)$,尽管只需要计算一个式子,但是涉及 $n$ 次幂……并且由于式子中出现了无理数 $\sqrt{5}$,无法直接用浮点数计算(会造成结果不准确),因此还需要用符号代数来计算,但是这样的话计算过程就得根据二项式定理展开再累加求和,进一步增加了计算量;
  • 空间复杂度为 $O(1)$,

代码略。

解法 5:查表,以空间换时间

一定要计算 $n$ 次吗,能不能更快?因为这是一个确定的数列,所以其实我们可以实现事先存储索引为 $2^k$($k \ge 0$ 且 $\max(2^k)$ 不超过整数范围)的数值,然后将输入的 N 分解为若干个 $2^k$ 的和,从而以空间换时间加速了运算。

假设数列长度为 $n$,那么

  • 时间复杂度为 $O(\log n)$,给力;
  • 空间复杂度为 $O(1)$,事先存储的内容大小是一定的,不受 $n$ 的影响。

参考