Aritalab:Lecture/Algorithm/BigO

まとめ

• O記法は関数の上限を与える

e.g. log n = O(n )

• Ω記法は関数の下限を与える

e.g. n² = Ω(n )

• Θ記法は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)

のように書くことが多いです。 また上の定義からは、

log n = O(n)

n = O(n²)

なのですが、このような書き方もほとんどせず、O記法をΘのようにみなして書きます。