3. 점근적 표기법(o-표기법, ω-표기법)

2021.09.23 - [알고리즘] - 0. 알고리즘 공부 시작

2021.09.24 - [알고리즘] - 1. 알고리즘(Algorithm)이란?

2021.09.26 - [알고리즘] - 2. 알고리즘 점근적 표기 및 시간 복잡도

2021.09.26 - [알고리즘] - 3. 점근적 표기법(o-표기법, ω-표기법)

2021.10.19 - [알고리즘] - 4. 정렬 - 1(선택정렬, 버블정렬, 삽입정렬)

2021.10.20 - [알고리즘] - 5. 정렬 - 2(합병 정렬, 퀵 정렬)

 

 

앞에서 재귀의 개념과 점근적 표기법 3가지를 알아봤다.

하지만 점근적 표기법은 그것 말고도 몇가지 더 있다.

 

오늘 소개해줄 3가지가 바로 그것이다.

만약 앞에 3가지가 생각이 안난다면 여기를 클릭해줘서 한번 보고 오는것을 추천한다.

 

1. o-표기법(리틀 오 표기법)

우선 앞에 설명한 개념인

Big O 와 little o의 차이점을 간단하게 설명하자면

 

O는 f(n)에 대해 >=를 만족하는 것을 표기한다면

o는 f(n)에 대해 >를 만족하는 것을 의미한다.

 

지난번 그래프를 다시한번 가져와서 비교해보자면

 

이 그래프의 선을 f(n)라 했을 때 O(n)은 그래프의 선부분에서 그 이하라고 했다면

o(n)은 저 선 미만의 영역을 의미한다.

 

즉 이하와 미만의 개념의 차이가 있다.

 

수학적으로 정의하자면

o(g(n)) = {f(n) | ∃n0 > 0 s.t. ∀c > 0 and n >= n0, f(n) < cg(n)}이다.

 

빅오의 표기법인

O(g(n)) = {f(n) | ∃ c > 0, n0 > 0 s.t. ∀ n > n0, f(n) <= cg(n)} 와 비교해서도 비슷하다.

다른점은 and로 ∀쪽에 조건이 붙었다는 것과 <=이 <로 바뀐 것이다.

 

이 역시도 구분해서 보자면

 

1. ∃ c > 0, n0 > 0

∃는 Exists란 의미로 존재한다는 뜻이다. 즉 0보다 큰 즉 양의 c와 n0가 존재 한다.

 

2. s.t. ∀c > 0 and n >= n0, f(n) < cg(n)

뒤의 조건이 만족하면 앞의 식이 만족된다는 의미이다.

 

3. ∀c > 0 and n >= n0

모든 양의 n과 c에 대해란 의미이다.

 

정리해보자면 모든 양의 n과 c가 f(n) < cg(n)을 만족한다면 양의 c와 n0가 존재한다는 의미이다.

 

위에서 말했듯이 그림에서 BigO가 선을 포함했다면 Little o는 선 미만의 지점들을 의미한다.

 

 

2. ω-표기법(리틀 오메가 표기법)

이 역시도 빅 오메가 표기법과 구분하면 이해하기 쉽다.

 

Ω는 f(n)에 대해 <=를 의미한다면

ω는 f(n)에 대해 <를 의미한다.

 

그래프의 선을 f(n)이라 했을 때 f(n)을 포함해서 이상인 영역이 Ω(n)라 한다면

그래프의 선 위의 영역이 ω(n)가 된다.

 

이상과 초과의 개념의 차이라 보면 된다.

 

수학적 표현으로 정의하자면

 

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

 

1. ∃n0 > 0

양의 n0가 있다.

 

2. s.t. ∀c > 0 and n >= n0, f(n) > cg(n)

뒤의 조건이 만족하면 앞의 식이 만족된다는 의미이다.

 

3. ∀c > 0 and n >= n0

모든 양의 n과 c에 대해란 의미이다.

 

즉 모든 양의 c와 n0보다 크거나 같은 n이 f(n) > cg(n)이다 란 의미이다.

 

 

 

혹시 틀린 부분이 있으면 댓글로 남겨주시기 바랍니다.

햇갈리거나 질문도 남겨주시면 감사합니다.