斐波那契数列 最优算法 js

斐波那契数列是一个经典的数列，每个数都是前两个数的和。在JavaScript中，可以使用迭代或递归的方式来计算斐波那契数列。下面是一个基于迭代的最优算法示例：

function fibonacci(n) {
  if (n <= 1) {
    return n;
  }

  let fibNMinus2 = 0;
  let fibNMinus1 = 1;
  let fibN = 0;

  for (let i = 2; i <= n; i++) {
    fibN = fibNMinus1 + fibNMinus2;
    fibNMinus2 = fibNMinus1;
    fibNMinus1 = fibN;
  }

  return fibN;
}

// 示例用法
console.log(fibonacci(5)); // 输出: 5
console.log(fibonacci(10)); // 输出: 55

这种算法的时间复杂度为 O(n)，其中 n 是斐波那契数列的索引。通过使用循环和仅保存前两个数的方法，可以有效地计算出较大索引的斐波那契数。