オーダー記法【ランダウの記号】 O記法

概要

オーダー記法（ランダウの記号）とは、関数の極限における値の変化を大まかに評価するための記法。ITの分野ではアルゴリズムの計算量の評価に用いられる。

関数を無限大など極限に飛ばしていった際に、おおよそどの程度のスピードで値が変化していくかを表す。例えば、f（x）=x²+x+1という関数のxを無限大に向けて増大させていくと、fの変化はほとんどがx²の項で決まり、第2項のxの影響は十分に小さくなる。

このことを記号「O」（ビッグオー）を用いて、f（x）=O（x²）のように記す。オーダーの評価では、最も影響の大きな項以外は無視する。また、定数の係数がある場合、定数倍の違いは極限においては大きな差ではないため無視する。

計算量のオーダー

計算機科学の計算量理論では、アルゴリズムの計算量を評価するためにこの考え方および記法を用いる。実際の計算にかかる時間はコンピュータの能力や入力するデータによって変わるが、入力するデータ量に対して計算回数がどのようなスピードで増えていくかはアルゴリズムごとに固有であるため、オーダー記法によって大まかに評価し、同種の別のアルゴリズムと比較することができる。

様々なアルゴリズムに登場する有名なオーダーには固有の名前が付けられている場合がある。最も計算量が少ないのはデータ量によらず定数回の計算で処理が完了するもので、「定数時間」と呼び「O（1）」と書き表す。

他のオーダーはデータ量n（通常はビット数）を使って表される。計算時間の短い方から、nの対数に比例する「対数時間」O（logn）、nに正比例する「線形時間」O（n）、nと対数の積に比例する「準線形時間」あるいは「線形対数時間」O（nlogn）、nの自乗に比例する「二乗時間」O（n²）、計算量が多項式で表される「多項式時間」O（n^c）（cは1以上の定数）、定数kのn乗に比例する「指数時間」O（kⁿ）、nの階乗に比例する「階乗時間」O（n!）などがよく知られる。

アルゴリズムによってはデータの規則性などによってまったく計算時間が変わることがあるため、最悪計算時間、平均計算時間、最良計算時間の3つに分けて評価する場合がある。例えば、高速な整列（ソート）アルゴリズムの代表として知られるクイックソートは、最良と平均の計算量が O（nlogn）と高速だが、特定の規則性のあるデータに対しては最悪 O（n²）かかってしまうことが知られている。