JavaScript斐波那契数列及其优化的示例分析

# JavaScript斐波那契数列及其优化的示例分析

斐波那契数列（Fibonacci sequence）是经典的编程问题，其定义为：`F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)（n≥2）`。本文将分析JavaScript中的实现及优化方案。

## 基础递归实现
```javascript
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n-1) + fibonacci(n-2);
}

问题：存在大量重复计算，时间复杂度为O(2^n)，性能极差。

优化方案

1. 记忆化（Memoization）
   通过缓存已计算结果降低复杂度：

const memo = [0, 1];
function fibMemo(n) {
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fibMemo(n-1) + fibMemo(n-2);
  return memo[n];
}

1. 迭代法
   空间复杂度优化至O(1)：

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

结论：记忆化适合多次调用场景，迭代法是性能最优解。 “`