[Section 1] 알고리즘의 분석 _ 빅-오메가 표기법

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

사실 알고리즘 분석에 있어서 빅-오메가 표기법은 그리 중요한 사항이 아니다. 하지만, 빅-오메가 표기법의 의의는 하한의 이해를 기반으로 자료구조의 알고리즘을 분석하는 데에 있다. 하한을 이해하면, 알고리즘의 최고 상태와 최악의 상태가 무엇인지 감이 올 것이다.

1. 빅 - 오메가 표기법의 정의

빅-오 표기법과 마찬가지로 빅-오메가 표기법의 수학적 정의를 먼저 보자.

 

" Ω(f(n))={g(n): 양의 정수 c와 n₀가 존재하여,

0 ≤ cf(n) ≤ g(n)을 만족하는 경우에 대해서 모든 n은 n₀ 보다 크거나 같다} "

 

여기에서 g(n)이 바로 점근적으로 가까운 하한(asymptotic tight lower bound)이 되는 것이다.

g(n)과 f(n)의 관계는 오메가 표기법에서와 동일할까? 다음의 예시를 보자.

 

" g(n) = Ω(f(n)) = n²+5 "

" f(n) = n² "

 

계수 c의 위치를 제외하고는 모두 동일하다.

 

빅-오메가 표기법도 빅-오와 동일하게 c와 n₀를 명시해주어야 한다. 예를 들어 위의 Ω(f(n))으로 나타낸 g(n)이 어떤 알고리즘의 함수라면, 하한 Ω(f(n))을 명시할 때는 c와 n₀를 같이 명시해주어야 한다는 것이다.

따라서 g(n)의 Ω(f(n))는 c=1, n₀=1이다. 

 

* 만약 빅 오메가 표기법으로 나타내면 O(g(n))으로 c=2, n₀=3이다. 

 

그렇다면 하한의 의미는 무엇일까?

2.  하한(Lower bound)의 의미

하한과 상한의 차이는 수학적 정의에서 c 계수 위치가 다르다는 것이었다. 그 의미는 알고리즘에 해당하는 함수, 예를 들면 f(n)에 가까워 지기 위한 함수 g(n)을 찾는 것이라고 할 수 있다. 즉, 상한은 f(n) 위에서 점근적으로 가까워지는 함수이고 하한은 f(n) 아래에서 점근적으로 가까워지는 함수라는 것이다.

 

위에서 제시한 예시를 함수로 그려보자.

 

"상한에 해당하는 cf(n) = 2n² _ c=2, n₀ =3"

 

"하한에 해당하는 cf(n) = n² _ c=1, n0 =1"

 

"알고리즘 함수 g(n) = n²+ 5"

상한과 하한의 의미

위 그림을 통해 하한과 상한의 의미가 보다 명확하게 이해될 것이다. 결과적으로 어떤 알고리즘의 상한과 하한은 데이터의 개수에 의존한다고 볼 수 있다.