アルゴリズムの性能評価基準
そもそもアルゴリズムとは何でしょう。
アルゴリズムとは、一言で言えば問題を解くための手順です。
あるインプットに対して、アルゴリズムを適用することで目的とする答えを導き出し、その答えをアウトプットとして吐き出します。
当然ながら、問題を解く方法(アルゴリズム)は一つだけとは限らず、複数の方法が考えられます。
優れたアルゴリズムとそうでないアルゴリズムがあるので、問題を効率良く解決するためには、適切なアルゴリズムを選ぶ必要があります。
では「優れた」アルゴリズムとはどのようなものでしょうか。
アルゴリズムの性能を比較する際、次の基準がよく用いられます。
・計算速度
・メモリ使用量
・計算の精度
これらの基準の中で最も重要視されているのが、計算速度です。
その理由は、他の基準はアルゴリズムによる差がそれほどないのに対し、計算速度はアルゴリズムによって大きく異なってしまうためです。
(正確な用語としては、計算速度のことを「時間計算量」、メモリ使用量のことを「空間計算量」と言い、単に「計算量」と言えば時間計算量を指す場合が多いです。以降は計算速度のことを計算量と呼ぶことにします。)
計算量を比較する際には、計算にかかった時間ではなく、計算回数を比較します。
理由は、計算に要する時間はコンピュータのスペックに依存するため、正確な比較ができないからです。
それに対し、一回の計算に要する時間は異なっていたとしても、計算回数自体はどのコンピュータでも同じです。
そのため、計算量の比較には計算回数を用いる方が本質的です。
アルゴリズムは、計算を繰り返す部分と、そうでない部分から構成されます。
計算を繰り返し行わない部分に関しては、実行時間が非常に短いため無視して構いません。
計算量に大きく影響するのは繰り返し処理の部分であるため、繰り返し回数が分かればアルゴリズムのおおよその計算量が分かると言えるでしょう。
計算量を改善したい時は、処理の繰り返し回数を減らすことが肝要です。
O記法
アルゴリズムの計算量を表現するためにしばしば用いられるのがO(ビッグオー)記法です。
O記法とは、「インプットされるデータ件数の増加に対し、アルゴリズムの繰り返し回数がどれだけ増加するか」を大雑把に表すものです。
データ件数nを用いて計算量がf(n)と表せる時、O(g(n))と書きます。
ここでg(n)はf(n)の最高次の項以外を落とし、さらに最高次の項の係数も無視したものです。
例えば
$ f(n) = 2n^2 + 5n + 1 $
なら、g(n)は
$ g(n) = n^2 $
となります。
$ f(n) = 10n^3 + 100 $
なら、g(n)は
$ g(n) = n^3 $
となります。
なぜこのようにするのかは数に対する感覚が身に付いていないとピンとこないかもしれませんが、大雑把に計算量を把握したい場合、最高次以外の項の影響や整数倍の影響などはたかがしれているため、無視して考えてもそれほど問題ありません。(nが十分大きい場合)
例をいくつか見てみましょう。
O(1)のアルゴリズムの場合、データ件数がどんなに多くなっても同じ時間で計算できます。
O(n)のアルゴリズムの場合、計算量はデータ件数に正比例します。
O(n^2)のアルゴリズムの場合、計算量はデータ件数の2乗に正比例します。
O記法を使用すると、コンピュータで実行せずともアルゴリズムのおおよその性能が分かるため、非常に有用です。
ここまで便宜上、単に計算量という表現を使っていましたが、同じアルゴリズムでも状況によって計算量の評価が大きく異なってしまうことが考えられます。
性能を正しく評価するためには、計算量には「最良時、最悪時、平均時」の3つのパターンがあることを知らなければなりません。
「10個の要素を持つ配列の中から、ある特定の要素を探す」という例を考えてみましょう。
線形探索を用いて、配列の先頭から順に目的の要素を探していきます。
最良のパターンは、配列の先頭に目的の要素がある場合です。この場合はたった1回の探索で済みます。
最悪のパターンは、配列の末尾まで探索を続けていってようやく目的の要素を見つけられた場合です。この場合は10回計算を行わなければなりません。
従って計算回数は、最良時は1回、最悪時はn回、平均的に言えばn/2回となります。
これをO記法で表すと、O(1)、O(n)、O(n)となります。
うっかり平均時をO(n/2)としないように注意して下さい。データが10個から20個(2倍)になった時、平均時の計算回数は5回から10回(2倍)となり、データ件数に正比例しています。このような場合はO(n)と表現します。先ほども書いたように、O記法においては定数倍は無視されるので、O(n/2)のような書き方はしません。何となくO記法が分かってきたでしょうか。
ご紹介した例のように、最良時、最悪時、平均時のどの場合を採用するかによって性能評価が大きく変わってしまうケースはよくあります。
ではどうするのかと言うと、多くの場合は「最悪時の場合」で性能を評価します。
場合によっては非常に高速に動作する可能性があるとしても、最悪な場合が考えられる限り、悪い方を基準とした方が無難だからです。
今まで説明を簡単にするために、単に計算量と呼んでいたものは、「最悪時の場合の計算量」を指していると思って下さい。
ただし、最悪なパターンというものがまず起こらないようなアルゴリズムにおいては、平均時の計算量を使うこともあるようです。
そのため、複数のアルゴリズムの性能を比較するときには、それらが、最悪時の計算量なのか、平均時の計算量なのかを確認する必要があります。
(なお、最良時の計算量を採用して比較することはほぼほぼ無いらしいです。)
また現実問題として、繰り返し回数を減らすことでアルゴリズムの見かけの性能が改善されたとしても、繰り返し1回分の処理が複雑になり、繰り返し回数は減らせても結果的に処理時間が長くなってしまった、となっては意味がないのでこの点は注意が必要です。
性能比較
性能分類としてよく使われるものを以下に示します。
・定数 : O(1)
(例 : 配列への添字アクセス)
・対数 : O(log n)
(例 : 二分探索)
・線形 : O(n)
(例 : 線形探索)
・線形対数 : O(n log n)
(例 : クイックソート)
・二乗 : O(n^2)
(例 : バブルソート)
・指数 : O(2^n)
(例 : 集合分割問題)
上記は性能の高い順に並んでいます。
分かりやすいようにグラフを書いたので参考にして下さい。
$ y = 1 $
$ y = \log x $
$ y = x $
$ y = x \log x $
$ y = x^2 $
$ y = 2^x $
非常にザックリとしたイメージですが、O(1)は最速、O(log n)はかなり早い、O(n)は普通、O(n log n)は少し遅い(この辺までの計算量に収まることが望ましい)、O(n^2)はかなり遅い、O(2^n)は大変遅いといった感覚です。
アルゴリズムの違いによって性能が上がる例として、例えば「平方根の近似値を求める」という問題があります。
興味がある方はこちらの記事をご覧下さい。
線形探索から二分探索へと手法を変えることで、性能を大幅に向上させています。(y=xとy=logxのグラフを見比べれば性能の差が一目瞭然ですね。)