斐波那契数列的若干解法 | 馨er的学习之路

转载y总的分享

今天来给大家介绍几个在面试中常用的、求解斐波那契数列问题的方法。

首先定义斐波那契数列问题：

定义 $a0 = 1$, $a_1 = 1$, $a_n = a{n-1} + a_{n-2}$，求 $a_n$ 是多少。
为了避免考虑整数溢出问题，我们求 $a_n \% p$ 的值，$p=10^9+7$。

算法1

递归。
递归计算的节点个数是 $O(2^n)$ 的级别的，存在大量重复计算。
时间复杂度是 $O(2^n)$，一秒内大约能算到第三四十项。

C++ 代码

const int MOD = 1000000007;
int f(int n)
{
    if (n <= 1) return 1;
    return (f(n - 1) + f(n - 2)) % MOD;
}

算法2

记忆化搜索。
开一个大数组记录中间结果，如果一个状态被计算过，则直接查表，否则再递归计算。
总共有 $n$ 个状态，计算每个状态的复杂度是 $O(1)$，所以时间复杂度是 $O(n)$。
一秒内算 $n=10^7$ 毫无压力，但由于是递归计算，递归层数太多会爆栈，大约只能算到 $n=10^5$ 级别。

C++ 代码

const int N = 100000, MOD = 1000000007;
int a[N];
int f2(int n)
{
    if (a[n]) return a[n];
    if (n <= 1) return 1;
    a[n] = f2(n - 1) + f2(n - 2);
    a[n] %= MOD;
    return a[n];
}

算法3

递推。
开一个大数组，记录每个数的值。用循环递推计算。
总共计算 $n$ 个状态，所以时间复杂度是 $O(n)$。
但需要开一个长度是 $n$ 的数组，内存将成为瓶颈，当 $n=10^8$ 时，需要的内存是 $\frac{4 * 10^8}{1024 \times 1024} \approx 381MB$。
分子中乘4是因为C++中 int 类型占4字节。

C++代码

const int N = 100000000, MOD = 1000000007;
int f3(int n)
{
    a[0] = a[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        a[i] = a[i - 1] + a[i - 2];
        a[i] %= MOD;
    }
    return a[n];
}

算法4

递归+滚动变量。
仔细观察我们会发现，递推时我们只需要记录前两项的值即可，没有必要记录所有值，所以我们可以用滚动变量递推。
时间复杂度还是 $O(n)$，但空间复杂度变成了 $O(1)$。

C++代码：

const int MOD = 1000000007;
int f4(int n)
{
    int x, y, z;
    x = y = 1;
    for (int i = 2; i <= n; i ++ )
    {
        z = (x + y) % MOD;
        x = y;
        y = z;
    }
    return z;
}

算法5

矩阵运算 + 快速幂。

快速幂算法的模板可以参考这里。
用算法4我们1秒内最多可以算到 $10^8$ 级别，那当 $n$ 更大时该怎么办呢？
可以先利用矩阵运算的性质将通项公式变成幂次形式，然后用平方倍增（快速幂）的方法求解第 $n$ 项。

首先我们定义向量

$\begin{equation} X_n = \begin{array}{ccc} [a_n & a_{n-1}] \end{array} , 边界： X_1 = \begin{array}{ccc} [a_1 & a_0] \end{array} \end{equation}$

然后我们可以找出矩阵：

$\begin{equation} A = \left [ \begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array} \right ] \end{equation}$

则有：

$X_n = X_{n-1} \times A$

所以：

$X_n = X_1 \times A^{n-1}$

由于矩阵具有结合律，所以我们可以先求出 $A^{n-1} \% P$，然后再用 $X_1$ 左乘，即可求出 $X_n$，向量 $X_n$ 的第一个元素就是 $a_n$。

时间复杂度分析：快速幂的时间复杂度是 $O(logn)$，所以算法5的时间复杂度也是 $O(logn)$。

C++代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>

using namespace std;

const int MOD = 1000000007;

void mul(int a[][2], int b[][2], int c[][2])
{
    int temp[][2] = {{0, 0}, {0, 0}};
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            for (int k = 0; k < 2; k ++ )
            {
                long long x = temp[i][j] + (long long)a[i][k] * b[k][j];
                temp[i][j] = x % MOD;
            }
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            c[i][j] = temp[i][j];
}


int f_final(long long n)
{
    int x[2] = {1, 1};

    int res[][2] = {{1, 0}, {0, 1}};
    int t[][2] = {{1, 1}, {1, 0}};
    long long k = n - 1;
    while (k)
    {
        if (k&1) mul(res, t, res);
        mul(t, t, t);
        k >>= 1;
    }

    int c[2] = {0, 0};
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
        {
            long long r = c[i] + (long long)x[j] * res[j][i];
            c[i] = r % MOD;
        }

    return c[0];
}


int main()
{
    long long n ;

    cin >> n;
    cout << f_final(n) << endl;

    return 0;
}