斐波那契数列 (Fibonacci Sequence)

算法原理

斐波那契数列是数学中非常著名的一个数列，定义如下：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n ≥ 2)。数列开始为：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...。这个问题虽然定义简单，但在算法学习中有重要意义，因为它展示了递归、记忆化搜索和动态规划等多种算法思想。朴素递归解法存在大量重复计算，时间复杂度为O(2^n)，而使用动态规划可以优化到O(n)。

算法步骤

1. 递归方法：直接按照定义实现，但存在大量重复计算
2. 记忆化搜索：使用数组或哈希表存储已计算的结果，避免重复计算
3. 动态规划：自底向上计算，从小到大依次计算每个斐波那契数
4. 空间优化：只保存必要的前两个数值，进一步优化空间复杂度

代码实现

public class Fibonacci {
    // 1. 朴素递归方法 (效率低)
    public static long fibRecursive(int n) {
        if (n <= 1) {
            return n;
        }
        return fibRecursive(n - 1) + fibRecursive(n - 2);
    }
    
    // 2. 记忆化递归方法
    public static long fibMemoization(int n) {
        long[] memo = new long[n + 1];
        return fibMemoHelper(n, memo);
    }
    
    private static long fibMemoHelper(int n, long[] memo) {
        if (n <= 1) {
            return n;
        }
        
        // 如果已经计算过，直接返回结果
        if (memo[n] != 0) {
            return memo[n];
        }
        
        // 计算并存储结果
        memo[n] = fibMemoHelper(n - 1, memo) + fibMemoHelper(n - 2, memo);
        return memo[n];
    }
    
    // 3. 动态规划方法
    public static long fibDP(int n) {
        if (n <= 1) {
            return n;
        }
        
        long[] dp = new long[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];
    }
    
    // 4. 空间优化的动态规划方法
    public static long fibOptimized(int n) {
        if (n <= 1) {
            return n;
        }
        
        long prev2 = 0;  // F(0)
        long prev1 = 1;  // F(1)
        long current = 0;
        
        for (int i = 2; i <= n; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        
        return current;
    }
    
    // 生成斐波那契数列
    public static long[] generateFibonacci(int count) {
        long[] fib = new long[count];
        if (count >= 1) fib[0] = 0;
        if (count >= 2) fib[1] = 1;
        
        for (int i = 2; i < count; i++) {
            fib[i] = fib[i-1] + fib[i-2];
        }
        
        return fib;
    }

    // 测试方法
    public static void main(String[] args) {
        int n = 10;
        
        System.out.println("计算斐波那契数列第 " + n + " 项:");
        
        // 注意：递归方法在n较大时会很慢，这里只演示较小的值
        if (n <= 35) {
            long startTime = System.nanoTime();
            long result1 = fibRecursive(n);
            long endTime = System.nanoTime();
            System.out.println("递归方法: " + result1 + 
                             " (耗时: " + (endTime - startTime) / 1000000.0 + " ms)");
        }
        
        long startTime = System.nanoTime();
        long result2 = fibMemoization(n);
        long endTime = System.nanoTime();
        System.out.println("记忆化方法: " + result2 + 
                         " (耗时: " + (endTime - startTime) / 1000000.0 + " ms)");
        
        startTime = System.nanoTime();
        long result3 = fibDP(n);
        endTime = System.nanoTime();
        System.out.println("动态规划方法: " + result3 + 
                         " (耗时: " + (endTime - startTime) / 1000000.0 + " ms)");
        
        startTime = System.nanoTime();
        long result4 = fibOptimized(n);
        endTime = System.nanoTime();
        System.out.println("优化DP方法: " + result4 + 
                         " (耗时: " + (endTime - startTime) / 1000000.0 + " ms)");
        
        // 生成前20项斐波那契数列
        System.out.println("\n前20项斐波那契数列:");
        long[] fibSequence = generateFibonacci(20);
        for (int i = 0; i < fibSequence.length; i++) {
            System.out.print(fibSequence[i] + " ");
        }
        System.out.println();
    }
}

应用场景

• 算法教学：作为递归和动态规划的经典教学案例
• 数学计算：在数学研究中用于分析黄金比例等性质
• 金融建模：在某些金融模型中用于模拟增长模式
• 自然界模拟：模拟植物生长、蜂巢结构等自然现象
• 编码理论：在某些编码算法中用作基础序列

优缺点