JavaScriptにおける高速なフィボナッチ数列の実装方法

1. 単純な再帰: 最も基本的な実装方法は再帰を使用する方法です。以下はその例です。

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

  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

この実装では、フィボナッチ数列のn番目の要素を計算するために、n-1番目とn-2番目の要素を再帰的に計算しています。しかし、この実装は効率的ではありません。同じ計算を何度も繰り返すため、大きなnに対して時間がかかることがあります。この実装の時間計算量は指数的に増加します。

function fibonacciMemoization(n, memo = {}) {
  if (n in memo) {
    return memo[n];
  }

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

  const result = fibonacciMemoization(n - 1, memo) + fibonacciMemoization(n - 2, memo);
  memo[n] = result;

  return result;
}

この実装では、計算済みの結果をmemoオブジェクトに保存し、再利用します。これにより、同じ計算を複数回行う必要がなくなります。したがって、計算時間が劇的に改善されます。この実装の時間計算量は線形になります。

3. ループと配列: さらなる最適化として、ループと配列を使用する方法があります。以下はその例です。

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

  const fib = [0, 1];

  for (let i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }

  return fib[n];
}

この実装では、フィボナッチ数列の各要素を順番に計算し、配列に保存しています。計算済みの結果を再利用できるため、効率的です。この実装の時間計算量も線形です。

このように、再帰を使った基本的な実装から、メモ化再帰やループと配列を組み合わせた実装まで、JavaScriptでフィボナッチ数列を高速に計算する方法はいくつかあります。適切な実装方法は、計算する数列の長さや性能要件に応じて選択する必要があります。