【アルゴリズム】JavaScriptでフィボナッチ数列問題を解く

はじめに

Qiitaの競技プログラミング研究月間ということで、アルゴリズムの記事を書いています。
今回はフィボナッチ数列問題をまとめました。

JavaScriptでアルゴリズムの勉強をされている方の参考になれば幸いです。
記事を順次まとめていきますので、その他の記事についてはマイページからご覧ください。

フィボナッチ数列

フィボナッチ数列のn項目を求めてください。

   fib(4) === 3

解答

2つの解法を試してみました。

以下では、n項目までのフィボナッチ数列を計算して、配列resultに格納しています。

index.js

function fib(n) {
  const result = [0, 1]; //初期状態

  for (i = 2; i <= n; i++) {
    const a = result[i - 1];
    const b = result[i - 2];

    result.push(a + b);
  }
  return result[n];
}

以下は再帰関数を使って解く方法です。

index.js

function fib(n) {
  if (n < 2) {
    return n;
  }

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

これをテストしてみると、n=3では1msしかかかりませんが、n=15だと588msもかかってしまいます。
1つ目の解法だとforループを1回まわすだけなので計算量がO(N)で済むのですが、再帰関数だと同じ計算を何度も行うので、引数nの値が大きくなるほど計算量が膨大になってしまいます。

 PASS  fib/test.js
  ✓ Fib function is defined (2 ms)
  ✓ calculates correct fib value for 1
  ✓ calculates correct fib value for 2
  ✓ calculates correct fib value for 3 (1 ms)
  ✓ calculates correct fib value for 4
  ✓ calculates correct fib value for 15 (588 ms)

再帰関数を使ったフィボナッチ数列の計算量を減らすためには、同じ引数に対する答えをメモ化します。

例えば、fib(6)を実行するとfib(4)が2回実行されますが、fib(4)が1回実行された時点でその答えをどこかに格納(メモ化)するようにします。
そして、fib(4)が2回目に実行されるときに再帰呼び出しを行わず、メモ化した値を直接返すようにします。
その結果、forループと同じO(n)の計算量で実装することができます。

以下でメモ化する関数memorize()を追加しています。

index.js

function memorize(fn) {
  const cache = {};
  return function (...args) {
    if (cache[args]) {
      return cache[args];
    }

    const result = fn.apply(this, args);
    cache[args] = result;

    return result;
  };
}

function fib(n) {
  if (n < 2) {
    return n;
  }

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

fib = memorize(fib);

これをテストしてみると、n=15で1msしかかかっていません。

  ✓ Fib function is defined
  ✓ calculates correct fib value for 1
  ✓ calculates correct fib value for 2
  ✓ calculates correct fib value for 3 (1 ms)
  ✓ calculates correct fib value for 4
  ✓ calculates correct fib value for 15 (1 ms)

参考資料