资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

递归算法之斐波那契数列（Fibonacci Sequence）详细解读

创作时间:

作者:

@小白创作中心

递归算法之斐波那契数列（Fibonacci Sequence）详细解读

引用

CSDN

https://blog.csdn.net/m0_61840987/article/details/143138507

斐波那契数列（Fibonacci Sequence）是一个经典的数列，最早由意大利数学家莱昂纳多·斐波那契（Leonardo Fibonacci）在13世纪提出。该数列从0和1开始，后续每个数字都是前两个数字的和。数学上可以通过递归关系定义：
F(0)=0, F(1)=1, F(n)=F(n−1)+F(n−2)forn≥2
也就是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

1. 斐波那契数列的特点

递归定义：每一项都是前两项的和，具备递推性质。
增长速度：斐波那契数列随着 n 的增大以指数方式增长，其增长速度近似于黄金比例。

2. 斐波那契数列的数学性质

2.1 黄金比例近似

随着 n 的增大，斐波那契数列的相邻两项之比逐渐接近黄金比例 ϕ：
即：
黄金比例与斐波那契数列的关系在几何学、艺术和自然界中都有广泛应用。

2.2 斐波那契数列的显式公式（Binet 公式）

通过递归公式可以推导出斐波那契数列的显式公式：

这个公式称为Binet 公式，尽管它的实际应用不多，但可以用来直接计算任意 n 位置的斐波那契数。

3. 斐波那契数列的几种计算方法

3.1 递归算法

最直接的实现方法是按照定义使用递归计算。代码如下：

// 递归实现
public static int fibonacciRecursive(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

时间复杂度

递归实现的时间复杂度为O(2^n)，因为每次递归调用会进行大量的重复计算。例如，计算 F(n)时，F(n−1) 和 F(n−2)会分别被多次计算。

3.2 动态规划算法

递归实现的问题在于它会进行重复计算，动态规划（Dynamic Programming, DP）通过存储已经计算过的子问题结果来避免这种重复。

// 动态规划实现
public static int fibonacciDP(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

时间复杂度

动态规划的时间复杂度为O(n)，因为每个子问题只计算一次。

空间复杂度

动态规划的空间复杂度为O(n)，因为需要一个数组来存储所有中间结果。

3.3 空间优化的动态规划算法

我们可以优化动态规划的空间复杂度。实际上，每次只需要保存最近的两个斐波那契数，因此我们可以用常数个变量来代替整个数组。

// 空间优化的动态规划
public static int fibonacciOptimized(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    int prev1 = 0, prev2 = 1;
    for (int i = 2; i <= n; i++) {
        int current = prev1 + prev2;
        prev1 = prev2;
        prev2 = current;
    }
    
    return prev2;
}

时间复杂度

时间复杂度依然是O(n)，但空间复杂度降到了O(1)，因为只需要常数个变量。

3.4 矩阵快速幂法

斐波那契数列也可以通过矩阵的幂来求解。斐波那契数列的递推关系可以表示为矩阵乘法：

我们可以通过快速幂算法在O(log n)的时间内计算矩阵的 n 次幂，从而得到 F(n)。

// 矩阵快速幂法实现斐波那契数列
public static int fibonacciMatrix(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    int[][] matrix = {{1, 1}, {1, 0}};
    matrixPower(matrix, n - 1);
    
    return matrix[0][0];
}
// 矩阵相乘
public static void multiply(int[][] a, int[][] b) {
    int x = a[0][0] * b[0][0] + a[0][1] * b[1][0];
    int y = a[0][0] * b[0][1] + a[0][1] * b[1][1];
    int z = a[1][0] * b[0][0] + a[1][1] * b[1][0];
    int w = a[1][0] * b[0][1] + a[1][1] * b[1][1];
    
    a[0][0] = x;
    a[0][1] = y;
    a[1][0] = z;
    a[1][1] = w;
}
// 矩阵快速幂
public static void matrixPower(int[][] matrix, int n) {
    if (n <= 1) return;
    
    int[][] base = {{1, 1}, {1, 0}};
    
    matrixPower(matrix, n / 2);
    multiply(matrix, matrix);
    
    if (n % 2 != 0) {
        multiply(matrix, base);
    }
}

时间复杂度

通过矩阵快速幂法，时间复杂度可以降低到O(log n)，因为我们使用了快速幂算法来计算矩阵的幂。