こんにちは、 @kz_morita です。 今回は、アルゴリズムの評価軸である計算量、そしてよく使われるオーダー記法についてまとめていきます。 アルゴリズムとは？ アルゴリズムというワードはよく聞くことが多いと思いますが、以下のように定義されていることが多いようです。 アルゴリズムとは、ある問題を解くのに 計算機などで機械的に解ける有限個の命令からなるプログラム であり、 問題のいずれの入力に対しても、有限時間で正しい解を出して停止する ものである 要は、問題を解くために、普通のプログラムのように任意の数の命令でかけて、無限ループしたり間違った答えを出さないものという感じの定義になります。 よく例に出されるのが、任意の要素を持つリストをソートするといったアルゴリズムがあると思います。 上記の定義に照らし合わせると、どんなリストを与えられても、有限個の命令で、(理論上) 有限時間で期待したソート順を返すのが、ソーティングアルゴリズムということが言えそうです。 以下のようなソーティングアルゴリズムを一度は聞いたことがあるのではないでしょうか？ バブルソート マージソート クイックソート etc… アルゴリズムの評価としての計算量 上記でアルゴリズムとはどんなものかを述べましたが、実際にプログラムを書くときには数種類のアルゴリズムからひとつを選んで実装するということになると思います。(ソーティングなどは、ライブラリの物を使うとは思いますが) そのときに、アルゴリズムの評価軸として用いられるのが 計算量 です。アルゴリズムが任意の入力に対して正しい答えをだすという前提の上で、アルゴリズムを比較したいとなったときには、アルゴリズムの計算時間が少ない方が優れたアルゴリズムであると言えます。 もちろん、実際の計算時間は実行されるハードウェアの影響などを受けるので、抽象化して単純化した指標が計算量となります。 アルゴリズムの計算量は一般的に、入力データ数に比例することが多いです。そのためデータ数 $n$ を用い、計算量は $n$ の関数として表現することができます。 ここでは以下のように 表します。 $$ 計算量 = T(n) $$ 具体例として、入力データ数と同じ回数だけの計算回数がかかるアルゴリズムがあるとします。 $n = 100$ の時に 計算回数が 100 回といった具合です。 その時の計算量は $$ T(n) = n $$ とあらわすことができそうです。入力データ数の 2 乗に比例するのであれば、 $$ T(n) = n^2 $$ のように表すことができます。 他にも以下のように様々なケースが考えらるでしょう。 $$ T(n) = 5n^3 + 2n + 100 $$