オー記法

読み：オーきほう
外語：O notation

品詞：名詞

関数の増加的傾向を示す記法の一つ。小文字のoと区別するためにビッグオー(big-oh)記法と呼ぶことも多い。アルゴリズムの計算量の増加傾向を検討するのによく使われている。

たとえばf(n) = 2n⁴ + 50n² + 200n + 3000 という関数がある場合、nが十分大きい場合は50n²、200n、3000といった数値は2n⁴の数値に比べて無視できるため、2n⁴の部分だけで関数の増加傾向が理解できるだろうと考える。

さらに2n⁴の2は定数倍項であるため、増加傾向の検討に必ずしも必要ない。そのため、通常はこの2も省略しn⁴だけで増加傾向を検討する。そのことを示すには、f(n) = O(n⁴)と書き、f(n)はn⁴のオーダーである、と表現する。

このような関数の省略を行なうことにより、数値の増加傾向の比較が簡単になるという利点がある。その代わり、実際の数値の正確さには欠けてしまう。

オー記法の定義は、関数f(n)、g(n)があり、f(n)≦cg(n)、n≧n0を満たすような定数cとn0が存在する時、f(n) = O[g(n)]。ただし、f(n) > 0、g(n) > 0。

計算量の増加傾向(下に行くほど増加傾向が高い)

リンク