Aritalab:Lecture/Algorithm/BigO

O記法

定義 O( )

関数 f(x) が正の定数 c と適当な値 x₀ に対して

f(x) ≤ c g(x)   (∀ x ≥ x₀)

を満たすならば

f(x) = O(g(x))

と書く。つまり、O記法は関数の上限を与える。

定義 Ω( )

関数 f(x) が正の定数 c と適当な値 x₀ に対して

f(x) ≥ c g(x)   (∀ x ≥ x₀)

を満たすならば

f(x) = Ω(g(x))

と書く。つまり、Ω記法は関数の加減を与える。

定義 Θ( )

関数 f(x) が

f(x) = O(g(x)), f(x) = Ω(g(x))

を満たすならば

f(x) = Θ(g(x))

と書く。

注

Ｏ、Ω、Θ記法で表しているのは関数の集合であるため、本当なら

f(x) ∈ O(nⁿ)

のように書かなくてはならない。しかし、便宜的に

O(n) + O(n) = O(n)、や

f(x) = x² + O(n)

のように書くことが多い。