正文

揭秘JS高效计算斐波那契数列第n项的秘诀

/0 浏览量
0320

斐波那契数列（Fibonacci sequence）是数学中一个著名的数列，它的每一项都是前两项的和。数列的前几项是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …。计算斐波那契数列的第n项是编程中的一个常见问题，但直接使用递归方法计算效率很低。本文将揭秘如何在JavaScript中高效地计算斐波那契数列的第n项。

1. 递归方法

最直观的方法是使用递归。递归方法简单，但效率低下，因为它会进行大量的重复计算。

function fibonacciRecursive(n) {
  if (n <= 1) {
    return n;
  }
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

这个递归方法的时间复杂度是O(2^n)，这意味着随着n的增加，计算时间会呈指数级增长。

2. 动态规划

为了避免重复计算，可以使用动态规划的方法来存储已经计算过的斐波那契数，从而降低时间复杂度。

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

这个动态规划方法的时间复杂度是O(n)，空间复杂度也是O(n)，因为它需要存储一个长度为n的数组。

3. 空间优化

在动态规划的基础上，可以通过只存储前两个数来进一步优化空间复杂度。

function fibonacciSpaceOptimized(n) {
  if (n <= 1) {
    return n;
  }
  let prev = 0;
  let curr = 1;
  for (let i = 2; i <= n; i++) {
    let next = prev + curr;
    prev = curr;
    curr = next;
  }
  return curr;
}

这个空间优化方法的时间复杂度仍然是O(n)，但空间复杂度降低到了O(1)。

4. 使用矩阵快速幂

斐波那契数列可以通过矩阵快速幂的方法来计算，这种方法的时间复杂度是O(log n)。

斐波那契数列可以表示为矩阵：

| F(n)   |     | 1 1 |     | F(n-1) |
|        |  =  |     |  *  |        |
| F(n-1) |     | 1 0 |     | F(n-2) |

计算矩阵的n次幂就可以得到斐波那契数列的第n项。

function matrixMultiply(a, b) {
  return [
    [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]]
  ];
}

function matrixPower(matrix, n) {
  if (n === 1) {
    return matrix;
  }
  if (n % 2 === 0) {
    let halfPower = matrixPower(matrix, n / 2);
    return matrixMultiply(halfPower, halfPower);
  } else {
    return matrixMultiply(matrix, matrixPower(matrix, n - 1));
  }
}

function fibonacciMatrixPower(n) {
  if (n <= 1) {
    return n;
  }
  let result = matrixPower([[1, 1], [1, 0]], n - 1);
  return result[0][0];
}

5. 总结

以上介绍了几种在JavaScript中高效计算斐波那契数列第n项的方法。递归方法简单但效率低下，动态规划方法效率较高但空间复杂度较高，空间优化方法进一步降低了空间复杂度，而矩阵快速幂方法则达到了最优的时间复杂度O(log n)。根据实际需求选择合适的方法可以帮助我们更好地处理斐波那契数列的计算问题。

-- 展开阅读全文 --