斐波那契数列

基本定义

斐波那契数列（Fibonacci Sequence）是一个经典的数列，其定义如下：

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2)（n ≥ 2）

即从第3项开始，每一项都等于前两项之和。前几项为：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

斐波那契数列的性质

1. 数列增长很快，随着n的增大，F(n)呈指数级增长。
2. 斐波那契数列在自然界中广泛存在，如兔子繁殖、植物叶序、贝壳螺旋等。
3. 具有黄金分割性质：相邻两项的比值趋近于黄金比例0.618。

常见算法实现

1. 递归法

最直观的实现方式，但效率较低，时间复杂度为 O(2^n)。

// 时间复杂度：O(2^n)
export function fibonacci_recursive(n: number): number {
  if (n <= 1) {
    return n;
  }
  return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}

2. 记忆化递归（自顶向下）

通过缓存已计算结果，避免重复计算，时间复杂度降为 O(n)。

function fibonacci_memo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo);
  return memo[n];
}

3. 动态规划（自底向上）

空间和时间复杂度均为 O(n)，适合大数据量。

function fibonacci_dp(n) {
  if (n <= 1) return n;
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

4. 动态规划-空间优化

只需保存前两项即可，空间复杂度降为 O(1)。

function fibonacci_optimized(n) {
  if (n <= 1) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

演示

斐波那契数列

递归查询斐波那契数列

时间复杂度：O(2^n)

查询

结果：请输入有效的 n (0~40)