1. 概述
本文将深入探讨斐波那契数列在 Java 中的实现方式。
重点是提供三种计算斐波那契数列第 n 项的方法，其中最后一种是常数时间复杂度的解法，性能拉满。对于有经验的开发者来说，这不仅是算法练习，更是理解时间复杂度优化的经典案例。
2. 斐波那契数列简介
斐波那契数列是一个每个项都等于前两项之和的数列，其前两项通常定义为 0 和 1。
例如，前 11 项为：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
在数学上，斐波那契数列 $ S(n) $ 的递推关系如下：
S(n) = S(n-1) + S(n-2), 其中 S(0) = 0, S(1) = 1
接下来，我们聚焦三种计算第 n 项的实现方式：
- 递归法
- 迭代法
- Binet 公式法（数学大法）
2.1. 递归法
最直观的实现就是直接翻译递推公式，代码简单粗暴：
public static int nthFibonacciTerm(int n) {
if (n == 0 || n == 1) {
return n;
}
return nthFibonacciTerm(n - 1) + nthFibonacciTerm(n - 2);
}
✅ 优点：代码简洁，逻辑清晰，一眼看懂。
❌ 缺点：性能灾难。存在大量重复计算。
⚠️ 踩坑提醒：以计算 n=6 为例，会重复计算 n=4 多次，调用树呈指数级膨胀。
其时间复杂度为 **O(Φⁿ)**，其中 Φ 是黄金比例，属于指数级别 ❌，n 稍大一点（比如 40）就卡得不行。
2.2. 迭代法
为了避免递归中的重复计算，迭代法通过“自底向上”动态规划思想，只保留前两项来推导下一项。
实现如下：
public static int nthFibonacciTerm(int n) {
if (n == 0 || n == 1) {
return n;
}
int n0 = 0, n1 = 1;
int tempNthTerm;
for (int i = 2; i <= n; i++) {
tempNthTerm = n0 + n1;
n0 = n1;
n1 = tempNthTerm;
}
return n1;
}
✅ 核心思路：
n0和n1分别保存前两项- 每轮循环更新这两个变量，向前推进
- 只需一次遍历，无重复计算
✅ 时间复杂度：O(n)
✅ 空间复杂度：O(1) —— 只用了几个变量，非常高效
这是在没有数学加持下的最优解法，实际开发中推荐使用。
2.3. Binet 公式法（数学开挂）
如果想把时间复杂度干到 **O(1)**，就得请出数学大神 Binet 的闭式公式。
斐波那契数列与黄金比例（golden ratio）Φ密切相关：
Φ = (1 + √5) / 2 ≈ 1.6180339887...
Binet 公式如下：
S(n) = (Φⁿ - (-Φ⁻ⁿ)) / √5
这意味着我们可以通过纯数学运算直接算出第 n 项，无需递推。
Java 实现：
public static int nthFibonacciTerm(int n) {
double squareRootOf5 = Math.sqrt(5);
double phi = (1 + squareRootOf5) / 2;
int nthTerm = (int) ((Math.pow(phi, n) - Math.pow(-phi, -n)) / squareRootOf5);
return nthTerm;
}
✅ 优势：**时间复杂度 O(1)**，理论上是最快的。
⚠️ 注意事项：
- 使用了
double浮点运算，存在精度误差 - 当
n较大时，浮点舍入误差会累积，可能导致结果偏差 - 对于
n > 70左右，结果可能不准确 ❌
📌 建议：仅用于 n 较小或对精度要求不高的场景。若需高精度，可结合 BigDecimal，但会牺牲性能。
3. 总结
| 方法 | 时间复杂度 | 空间复杂度 | 是否推荐 |
|---|---|---|---|
| 递归法 | O(Φⁿ) | O(n) | ❌ |
| 迭代法 | O(n) | O(1) | ✅ 推荐 |
| Binet 公式 | O(1) | O(1) | ⚠️ 小 n 可用 |
- 递归法：教学意义大于实用价值，面试时写出要说明复杂度问题。
- 迭代法：简单高效，生产环境首选。
- Binet 公式：秀操作可以，但要注意精度陷阱。
所有示例代码已托管至 GitHub：https://github.com/dev-zzo/java-algorithms
欢迎 star & fork，持续更新中。