はじめに
アルゴリズムを比較する基準として、アルゴリズムの計算量がある。
それぞれのアルゴリズムが答えを出すまでに要する計算時間などを計算し、比較する。
O-記法
一般的に、計算量はO-記法を用いて表す。
O-記法は、関数の挙動を分かりやすい別の関数を目安にして記述するための記法である。
例えば、関数 f(n) が g(n) と同じような挙動をする場合、
f(n) = O(g(n))
と表記する。
関数の挙動、つまり計算量の増加にさほど関係しない項は無視し、
また主要項の係数も無視する。
アルゴリズムの計算量が O(g(n)) であるとき、このアルゴリズムのオーダーが
g(n) である、という。
よく使われるオーダー
増加率の低いものから順に並べる。
つまり、計算量の小さい順。
| オーダー | アルゴリズムの例 |
|---|---|
| O(1) | |
| O(log n) | バイナリサーチ |
| O(n) | 線形サーチ |
| O(n^2) |
なお、アルゴリズムのオーダーを表記する際、
対数の底が省略されていた場合はその対数の底は2であることが多い。
リファレンス
-
- O-記法について書いてある。
-
- 対数関数 log n について。