異なるアルゴリズムによるフィボナッチ数列の実行速度の違い

はじめに

こんにちは。

最近、アルゴリズムを勉強をしている中で、学校の授業でも扱ったことがあるフィボナッチ数列に出会いました。
今回は、全探索と動的計画法といったアルゴリズムでフィボナッチ数列の解を求めました。
その際に、この2つのアルゴリズムの実行速度を比べてみると圧倒的に違ったので、その結果を記事にしてみました。
アルゴリズムの重要性も伝わるのかなと思います。

ただし、この記事では、フィボナッチ数列や、全探索、動的計画法の解説はしていないので、もし分からない場合は調べてみてください。また、使用したプログラミング言語はC++です。よろしくお願いします。

環境

• Windows 10 home
• gcc 8.2.0
• Intel Core i9-7900X

全探索によるフィボナッチ数列のソースコード

Fibonacci1.cpp

# include <bits/stdc++.h>
# include <chrono>

using namespace std;
typedef long long ll;

ll fib(ll n){
  if(n <= 1){
    return n;
  }else{
    return fib(n-1) + fib(n-2);
  }
}

int main() {

  ll N;
  cin >> N;

  const auto startTime = chrono::system_clock::now();

  cout << fib(N) << endl;

  const auto endTime = chrono::system_clock::now();
  const auto timeSpan = endTime - startTime;
  cout << "処理時間:" << chrono::duration_cast<chrono::milliseconds>(timeSpan).count() << "[ms]" << endl;
}

実行結果

コンソール上に上記のような実行結果になりました。
全探索で50番目のフィボナッチ数を求めようとした結果、解が12586269025で処理時間が112240ミリ秒となりました。

動的計画法によるフィボナッチ数列のソースコード

Fibonacci2.cpp

# include <bits/stdc++.h>
# include <chrono>

using namespace std;
typedef long long ll;

ll memo[1000];

ll fib(ll n){
  if(n <= 1){
    return n;
  }else if(memo[n] != 0){
    return memo[n];
  }else{
    return memo[n] = fib(n-1) + fib(n-2);
  }
}

int main() {

  ll N;
  cin >> N;

  const auto startTime = chrono::system_clock::now();

  cout << fib(N) << endl;

  const auto endTime = chrono::system_clock::now();
  const auto timeSpan = endTime - startTime;
  cout << "処理時間:" << chrono::duration_cast<chrono::milliseconds>(timeSpan).count() << "[ms]" << endl;
}

実行結果

コンソール上に上記のような実行結果になりました。
動的計画法で50番目のフィボナッチ数を求めようとした結果、解が12586269025で処理時間が1ミリ秒となりました。

おわり

いかがだったでしょうか。
同じ解を求めるのにもかかわらず、アルゴリズムが違うだけで、処理時間の差が10万倍以上ありました。
こんなに分かりやすく違いが出たので、アルゴリズムの重要性をより実感しました。

もし興味があれば、ぜひ試してみてください。
ここまで読んでいただき、ありがとうございました。