オーダー記法による時間計算量の表現
アルゴリズムの効率を評価する際、入力データの大きさに対する計算時間の増加を表す指標として、オーダー記法(Big O Notation)が用いらる。オーダー記法は、アルゴリズムの時間計算量を、入力サイズnに対する関数の最も影響の大きい項を取り出して表現する。
代表的な時間計算量の説明
O(1) - 定数時間
入力サイズによらず、常に一定の時間がかかるアルゴリズム。例えば、配列の先頭要素にアクセスする操作など。
O(log n) - 対数時間
入力サイズが2倍になる度に、計算時間は一定分増加する。二分探索などの効率的なアルゴリズムがこのクラスに属する。
O(n) - 線形時間
入力サイズに比例して計算時間が増加する。先ほど説明した線形探索がこのクラスに属する。
O(n log n) - n log nの時間
高速ソートアルゴリズム(マージソート、クイックソートなど)の典型的な計算量。
O(n^2) - 二次時間
入力サイズの二乗に比例して計算時間が増加する。単純な多重ループアルゴリズムはこのクラスに属することが多い。
O(2^n) - 指数時間
最も計算量が大きいクラス。総当りアルゴリズムなどが該当する。実用的ではない。
オーダー記法は、最悪の場合の計算量を表すが、ベストケースやアベレージケースについても議論されることがある。時間計算量が小さいほど、アルゴリズムは効率的で、大規模な入力に対しても適用可能となる。
