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

Huko·2023년 3월 16일
0

알고리즘

목록 보기
9/11

점근적 표기법

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)이다 란 의미이다.

profile
iOS 개발자 지망생

0개의 댓글