Fibonacci 斐波那契
算法定义
斐波那契（Fibonacci）数列是一个经典的数学序列，其定义为：
- 第 0 项为 0，第 1 项为 1
- 从第 2 项开始，每一项都等于前两项之和，即
F(n) = F(n-1) + F(n-2)
斐波那契算法是用于计算该序列中第 n 项的算法，其核心是通过不同策略实现上述递归关系，解决序列计算问题。
1 1 2 3 5 8 13 21 ...
fib 0 1 位置 = 1
fib(n) = fib(n-1) + fib(n-2)
斐波那契数列(fibonacci sequence)、重叠子问题（overlap sub-problem）
算法思路
斐波那契算法的核心是实现递推关系 F(n) = F(n-1) + F(n-2)，不同实现方式的思路如下：
- 递归思路：直接通过函数自我调用计算，将大问题分解为小问题
- 递推思路：从初始项开始，迭代计算至目标项
- 矩阵快速幂思路：利用矩阵乘法的性质，通过快速幂优化计算
- 公式思路：使用通项公式直接计算（存在精度问题）
算法复杂度
| 实现方式 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 递归版 | O(2ⁿ) | O(n) |
| 基本递推版 | O(n) | O(n) |
| 优化递推版 | O(n) | O(1) |
| 矩阵快速幂版 | O(log n) | O(1) |
| 公式版 | O(1) | O(1) |
所有实现的最坏、最好和平均时间复杂度一致，因为计算逻辑不受输入数据分布影响。
应用场景
- 数学问题（黄金分割、数列研究）
- 算法优化（斐波那契查找、动态规划基础案例）
- 生物领域（种群增长模型）
- 金融分析（复利计算模型）
- 计算机科学（递归与迭代教学、算法复杂度分析案例）
优点与缺点
不同实现方式的优缺点对比：
- 递归版：
- 优点：代码简洁，符合数学定义
- 缺点：效率极低，存在大量重复计算，递归深度有限制
- 递推版：
- 优点：效率高，实现简单，无栈溢出风险
- 缺点：需要遍历至目标项，不适合超大规模 n
- 矩阵快速幂版：
- 优点：时间复杂度低（O (log n)），适合超大 n
- 缺点：实现复杂，理解门槛高
- 公式版：
- 优点：理论上可直接计算，时间复杂度 O (1)
- 缺点：浮点数精度限制，无法计算大 n
Java 实现及优化版本
import java.math.BigInteger;
public class Fibonacci {
// 1. 递归版（效率最低，仅作演示）
public static long fibonacciRecursive(int n) {
if (n < 0) {
throw new IllegalArgumentException("n不能为负数");
}
// 基线条件
if (n == 0) return 0;
if (n == 1) return 1;
// 递归计算
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
// 2. 基本递推版（存储所有中间结果）
public static long fibonacciIterativeBasic(int n) {
if (n < 0) {
throw new IllegalArgumentException("n不能为负数");
}
if (n == 0) return 0;
if (n == 1) return 1;
// 存储所有中间结果
long[] fib = new long[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
// 3. 空间优化递推版（仅保留最近两项）
public static long fibonacciIterativeOptimized(int n) {
if (n < 0) {
throw new IllegalArgumentException("n不能为负数");
}
if (n == 0) return 0;
if (n == 1) return 1;
long prevPrev = 0; // F(n-2)
long prev = 1; // F(n-1)
long current = 0; // F(n)
for (int i = 2; i <= n; i++) {
current = prev + prevPrev;
prevPrev = prev;
prev = current;
}
return current;
}
// 4. 记忆化递归版（解决重复计算问题）
public static long fibonacciMemoization(int n) {
if (n < 0) {
throw new IllegalArgumentException("n不能为负数");
}
// 使用数组存储已计算结果
long[] memo = new long[n + 1];
for (int i = 0; i <= n; i++) {
memo[i] = -1; // 初始化标记未计算
}
return fibonacciMemoHelper(n, memo);
}
private static long fibonacciMemoHelper(int n, long[] memo) {
if (n == 0) return 0;
if (n == 1) return 1;
// 检查是否已计算
if (memo[n] != -1) {
return memo[n];
}
// 计算并存储结果
memo[n] = fibonacciMemoHelper(n - 1, memo) + fibonacciMemoHelper(n - 2, memo);
return memo[n];
}
// 5. 矩阵快速幂版（适合超大n，O(log n)时间）
public static long fibonacciMatrix(int n) {
if (n < 0) {
throw new IllegalArgumentException("n不能为负数");
}
if (n == 0) return 0;
// 矩阵 [[1,1],[1,0]] 的n-1次方
long[][] matrix = {{1, 1}, {1, 0}};
matrix = matrixPower(matrix, n - 1);
// 结果为矩阵[0][0]
return matrix[0][0];
}
// 矩阵乘法
private static long[][] matrixMultiply(long[][] a, long[][] b) {
return new long[][] {
{a[0][0] * b[0][0] + a[0][1] * b[1][0],
a[0][0] * b[0][1] + a[0][1] * b[1][1]},
{a[1][0] * b[0][0] + a[1][1] * b[1][0],
a[1][0] * b[0][1] + a[1][1] * b[1][1]}
};
}
// 矩阵快速幂（二分法）
private static long[][] matrixPower(long[][] matrix, int power) {
// 初始化为单位矩阵
long[][] result = {{1, 0}, {0, 1}};
while (power > 0) {
if (power % 2 == 1) {
result = matrixMultiply(result, matrix);
}
matrix = matrixMultiply(matrix, matrix);
power /= 2;
}
return result;
}
// 6. 支持大整数的版本（解决long溢出问题）
public static BigInteger fibonacciBigInteger(int n) {
if (n < 0) {
throw new IllegalArgumentException("n不能为负数");
}
if (n == 0) return BigInteger.ZERO;
if (n == 1) return BigInteger.ONE;
BigInteger prevPrev = BigInteger.ZERO;
BigInteger prev = BigInteger.ONE;
BigInteger current = BigInteger.ZERO;
for (int i = 2; i <= n; i++) {
current = prev.add(prevPrev);
prevPrev = prev;
prev = current;
}
return current;
}
public static void main(String[] args) {
int n = 30;
System.out.println("递归版 F(" + n + ") = " + fibonacciRecursive(n));
System.out.println("基本递推版 F(" + n + ") = " + fibonacciIterativeBasic(n));
System.out.println("优化递推版 F(" + n + ") = " + fibonacciIterativeOptimized(n));
System.out.println("记忆化递归版 F(" + n + ") = " + fibonacciMemoization(n));
System.out.println("矩阵快速幂版 F(" + n + ") = " + fibonacciMatrix(n));
System.out.println("大整数版 F(100) = " + fibonacciBigInteger(100));
}
}
各版本优化说明
- 递归版： 直接实现数学定义，代码最简单但效率极低，存在大量重复计算（如计算 F (5) 需重复计算 F (3)、F (2) 等），仅适合理解原理，不适合实际应用。
- 基本递推版： 通过迭代计算，避免重复计算，时间复杂度优化至 O (n)，但需存储所有中间结果，空间复杂度 O (n)。
- 空间优化递推版： 仅保留最近两项结果，将空间复杂度从 O (n) 降至 O (1)，是实际应用中的首选方案，平衡了效率和实现复杂度。
- 记忆化递归版： 通过缓存已计算结果解决递归版的重复计算问题，时间复杂度 O (n)，空间复杂度 O (n)，适合需要递归形式的场景。
- 矩阵快速幂版： 利用矩阵乘法性质和快速幂算法，将时间复杂度降至 O (log n)，适合计算超大 n 值（如 n > 10⁶），但实现较复杂。
- 大整数版： 使用
BigInteger解决 long 类型的溢出问题，可计算非常大的斐波那契数（如 n=10000），适合需要高精度结果的场景。
斐波那契算法是算法设计的经典案例，其不同实现方式展示了递归、迭代、动态规划、矩阵运算等多种算法思想，是理解算法优化过程的绝佳范例。在实际开发中，应根据 n 的大小和精度要求选择合适的实现方式。