Aritalab:Lecture/Algorithm/BigO

Revision as of 14:09, 18 October 2010

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))

と書く。