점근적 표기법

점근적 표기법 

우리는 알고리즘의 복잡도를 점근적 표기법으로 표기한다.

 

대표적인 표기법으로 3가지가 있다.

빅오 -> 점근적 상한

세타 -> 점근적 동등

오메가 -> 점근적 하한

 

빅오표기법

만약 ­Ο(n^2)이라면 최고차항이 n^2을 넘지않는 집합을 말하는 것이다. 즉 n, n^2 + 3n + 2, nlogn등 모두 포함이 된다.

기껏해야 n^2이라는 뜻이다.  만약 nlogn을 Ο(n^2)으로 표현해도 틀린말은 아니지만 더욱 정확하게 Ο(nlogn)으로 쓰는것이 더욱 적절한 정답이다. 

 

수학적 정의

O(g(n)) = { f(n) | ∃c > 0, n0 ≥ 0 s.t.∀n ≥ n0, cg(n) ≥ f(n) }

쉽게 설명해서 말하자면 충분히 큰 n에 대해서 cg(n) ≥ f(n)을 만족하는 상수 c가 존재한다. f(n) = O(g(n)) ⇒ f 는 g보다 빠르게 증가하지 않는다

 

오메가표기법

오메가 표기법은 빅오표기법과는 반대로 Ω(n)이라면 최고차항이 n보다 작지않는 모든 함수의 집합을 뜻한다.

 

수학적 정의

Ω(g(n)) = { f(n) | ∃c > 0, n0 ≥ 0 s.t.∀n ≥ n0, cg(n)≤f(n) }

(n) = Ω(g(n)) ⇒ f는 g보다 느리게 증가하지 않는다

 

 

세타표기법

Θ(n)이라면 최고차항이 n이 넘지않는 모든 함수 집합을 뜻한다.  

 

수학적 정의

Θ( g(n) ) = O( g(n) ) ∩ Ω( g(n) )

f(n) = Θ(g(n)) ⇒ f는 g와 같은 정도로 증가한다