BFE.devでのAI解答例 - JavaScript コーディング問題
86. Fibonacci数を返す

回答

以下は時間複雑性O(n)、空間複雑性O(1)の実装例です。

function fib(n) {
  if (n < 1) return 0;
  let a = 0;
  let b = 1;
  for (let i = 2; i <= n; i++) {
    const sum = a + b;
    a = b;
    b = sum;
  }
  return b;
}

最初の二つの数字が0と1であるため、nが0または1の場合はそれぞれ0と1を返します。

それ以外の場合はforループを使用し、最後の二つの数字を足して新しい数字を生成する処理をn回繰り返します。この方法により、n番目のFibonacci数を取得できます。

時間複雑性はO(n)であるため、nが増加するにつれて処理時間が増加します。一方、空間複雑性はO(1)であるため、追加のメモリスペースを必要としません。