[알고리즘] 알고리즘의 점근적 표기

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.
참고교재: 쉽게 배우는 알고리즘(문병로)

 

알고리즘의 점근적 표기란

알고리즘의 점근적 표기는 알고리즘의 효율성을 표현하는 데 사용되는 수학적 표기법입니다. 이는 알고리즘의 시간 복잡도와 공간 복잡도를 평가하는 데 사용되며, 특히 입력의 크기가 커질 때 알고리즘의 동작을 설명하는 데 유용합니다

 

점근적 표기법은 일반적으로 5가지가 있습니다.

 

1. 빅 오(Big O)
2. 빅 오메가(Big Ω)
3. 빅 세타(Big Θ)

4. 리틀 오(Little o)

5.리틀 오메가(Little ω)

 

점근적 표기, 출처: 위키백과

 

1. 빅 오(Big O)

주어진 함수 f(n)이 O(g(n))이라고 할 때, 양의 상수 c와 n0이 존재하여 모든 n > n0에 대해 |f(n)| <= c * |g(n)|이 성립한다면, 이를 f(n)이 g(n)의 빅 오라고 표현합니다.

2. 빅 오메가(Big Ω)

주어진 함수 f(n)이 Ω(g(n))이라고 할 때, 양의 상수 c와 n0이 존재하여 모든 n > n0에 대해 |f(n)| >= c * |g(n)|이 성립한다면, 이를 f(n)이 g(n)의 빅 오메가라고 표현합니다.

3. 빅 세타(Big Θ)

주어진 함수 f(n)이 Θ(g(n))이라고 할 때, 양의 상수 c1, c2와 n0이 존재하여 모든 n > n0에 대해 c1 * |g(n)| <= |f(n)| <= c2 * |g(n)|이 성립한다면, 이를 f(n)이 g(n)의 빅 세타라고 표현합니다.

4. 리틀 오(Little o)

주어진 함수 f(n)이 o(g(n))이라고 할 때, 모든 양의 상수 c에 대해 적절한 n0가 존재해서 n > n0에 대해 |f(n)| < c * |g(n)|이 성립한다면, 이를 f(n)이 g(n)의 리틀 오라고 표현합니다.

5.리틀 오메가(Little ω)

주어진 함수 f(n)이 ω(g(n))이라고 할 때, 모든 양의 상수 c에 대해 적절한 n0가 존재해서 n > n0에 대해 |f(n)| > c * |g(n)|이 성립한다면, 이를 f(n)이 g(n)의 리틀 오메가라고 표현합니다.

 

점근표기 예제

1) 어떤 알고리즘의 소요시간이 다음과 같을 때 해당하는 점근표기는?

 

알고리즘: 6n^2+8

점근 표기 Ο(n), Ω(n), Θ(n), Ο(n^2), Ω(n^2), Θ(n^2)

 

답: Ω(n), Ο(n^2), Ω(n^2), Θ(n^2)

 

점화식의 점근적 분석 방법

점화식의 점근적 분석 방법은 세가지가 있습니다.

 

1. 반복 대치 

2. 추정후 증명 

3. 마스터 정리

 

1. 반복 대치

더 작은 문제에 대한 함수로 반복해서 대치해 나가는 해법입니다.

merge sort의 점화식을 반복대치로 증명

 

2. 추정후 증명

결론을 추정하고 수학적 귀납법으로 이용하여 증명하는 방법입니다.

• Mergesort 의 점화식은 T(n ) = 2T(n/2) + n
• T(n ) = O( nlogn) 일 것이라 추정
• 충분히 큰 n 에 대해서 T(n ) ≤ c*nlogn 을 만족하는 양의 상수 c 가 존재함을 증명

 

3. 마스터 정리

형식에 맞는 점화식의 복잡도를 바로 알 수 있습니다.

마스터정리를 이용한 증명 예시