TypeScriptでフィボナッチ数列を効率的に実装する方法

フィボナッチ数列は、プログラミング学習者やアルゴリズムの学習者にとって非常に親しみやすい問題の一つです。TypeScriptでの実装方法を解説しながら、効率的な実装のポイントを紹介します。

[目次を開く]

フィボナッチ数列とは？ TypeScriptでの実装例 1. 再帰による実装 2. メモ化を用いた効率化 3. 反復処理による実装 4. 行列の累乗を用いた高度な実装フィボナッチ数列を活用するシーンまとめ

フィボナッチ数列とは？

フィボナッチ数列は、以下のような数列です：

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

各数は、その直前の2つの数を足した値になります。式で表すと次のようになります：

F(0)=0

F(1)=1

F(n)=F(n−1)+F(n−2) （n≥2n）

TypeScriptでの実装例

1. 再帰による実装

再帰はシンプルな方法ですが、効率面で問題があります。

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

console.log(fibonacciRecursive(10)); // 55

このコードは短く書ける反面、同じ計算を何度も繰り返すため、大きな数値には向いていません。計算量は指数関数的に増加します。

2. メモ化を用いた効率化

再帰に「メモ化」を組み合わせることで、計算済みの結果を保存し、効率化を図ることができます。

function fibonacciMemo(n: number, memo: Map<number, number> = new Map()): number {
  if (n < 2) return n;

  if (memo.has(n)) {
    return memo.get(n)!;
  }

  const result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

console.log(fibonacciMemo(50)); // 12586269025

メモ化によって計算量は O(n)に減少します。

3. 反復処理による実装

最も効率的かつ簡単な方法がループを用いる方法です。

function fibonacciIterative(n: number): number {
  if (n < 2) return n;

  let prev = 0;
  let current = 1;

  for (let i = 2; i <= n; i++) {
    const next = prev + current;
    prev = current;
    current = next;
  }

  return current;
}

console.log(fibonacciIterative(50)); // 12586269025

この方法では追加のメモリをほとんど使用せず、計算量は O(n) です。

4. 行列の累乗を用いた高度な実装

フィボナッチ数列は行列を使って効率的に求めることができます。この方法では O(log ⁡n) の計算量を達成できます。

function matrixMultiply(a: number[][], b: number[][]): number[][] {
  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: number[][], n: number): number[][] {
  let result = [
    [1, 0],
    [0, 1],
  ]; // 単位行列
  let base = matrix;

  while (n > 0) {
    if (n % 2 === 1) {
      result = matrixMultiply(result, base);
    }
    base = matrixMultiply(base, base);
    n = Math.floor(n / 2);
  }

  return result;
}

function fibonacciMatrix(n: number): number {
  if (n <= 1) return n;

  const fibMatrix = [
    [1, 1],
    [1, 0],
  ];

  const result = matrixPower(fibMatrix, n - 1);
  return result[0][0];
}

console.log(fibonacciMatrix(50)); // 12586269025

行列の累乗を利用した方法は、非常に大きな数値でも高速に計算できます。

フィボナッチ数列を活用するシーン

フィボナッチ数列は単なる学術的な題材だけでなく、以下のような実用的な用途にも使われています：

アルゴリズム最適化
ダイナミックプログラミングや分割統治法の練習問題として使われることが多いです。
自然現象のモデリング
フィボナッチ数列は植物の葉の配置やひまわりの種の配置など、自然界のパターンを説明するのに使われます。
金融工学
株価の変動予測にフィボナッチ比率が応用されています。

まとめ

TypeScriptでフィボナッチ数列を実装する際には、用途や対象とする数値の大きさに応じて適切なアルゴリズムを選ぶことが重要です。再帰はシンプルですが非効率的であり、メモ化や反復、行列の累乗を利用することで効率を大幅に向上できます。

アルアカ - Arcadia Academia