3. 점근적 표기법 - Big-Ω(빅 오메가), Big-θ(빅 세타), Big-O(빅 오)

점근적 표기법

- 알고리즘의 성능은 입력의 크기가 충분히 클 때의 성능이 중요하다. 그래서 알고리즘의 수행 시간은 항상 입력의 크기가 충분히 클 때를 분석한다. 즉, 입력이 \(\infty\)일 때를 분석하기 위해 점근적 분석을 해야한다.

- 점근적 분석을 위해서 사용되는 표기법이 점근적 표기법이다. 점근적 표기법의 종류에는 여러 가지가 있지만 그 중 알고리즘에서 쓰이는 예는 \(\lim_{x\rightarrow \infty}\)을 사용한 점근적 표기법이다.

 

점근적 표기법에서 헷갈리지 말아야 할 것

증가율이 더 빠르다 = 알고리즘이 더 느리게 수행된다.

증가율이 더 느리다 = 알고리즘이 더 빠르게 수행된다.

 

1) Big - Ω (빅 오메가) 표기법

Ω(g(n)) 는 g(n)이라는 함수보다 증가율이 같거나 더 빠른 함수들의 집합이다. 

빨간색 영역(함수 g 포함)의 모든 함수들은 Ω(g)에 해당한다.

예)

Ω \((n^{2}) \ni 2n^{3} + 3n^{2} - 25\)

\(2n^{3} + 3n^{2} - 25\)은 g(n) = \(n^{2}\)보다 증가율이 더 빠른 함수이므로 Ω \((n^{2})\)이 맞다.

Ω \((n^{2}) \ni 10n^{2} + 3n - 25\)

\(10n^{2} + 3n - 25\)은 g(n) = \(n^{2}\)과 증가율이 같은 함수이므로 Ω \((n^{2})\)이 맞다.

Ω \((n^{2})\) ∌ \(10nlogn + 5n\)

\(10nlogn + 5n\)은 g(n) = \(n^{2}\)보다 증가율이 더 느린 함수이므로 Ω \((n^{2})\)이 아니다

2) Big - θ (빅 세타) 표기법

θ(g(n)) 는 g(n)이라는 함수보다 증가율이 같은 함수들의 집합이다. 

빨간색 영역(함수 g 포함)의 모든 함수들은 θ(g)에 해당한다.

예)

θ \((n^{2})\) ∌ \(2n^{3} + 3n^{2} - 25\)

\(2n^{3} + 3n^{2} - 25\)은 g(n) = \(n^{2}\)보다 증가율이 더 빠른 함수이므로 θ \((n^{2})\)이 아니다.

θ \((n^{2}) \ni 10n^{2} + 3n - 25\)

\(10n^{2} + 3n - 25\)은 g(n) = \(n^{2}\)과 증가율이 같은 함수이므로 θ \((n^{2})\)이 맞다.

θ \((n^{2})\) ∌ \(10nlogn + 5n\)

\(10nlogn + 5n\)은 g(n) = \(n^{2}\)보다 증가율이 더 느린 함수이므로 θ \((n^{2})\)이 아니다

 

3) Big - O (빅 오) 표기법

O(g(n)) 는 g(n)이라는 함수보다 증가율이 같거나 더 느린 함수들의 집합이다. 

빨간색 영역(함수 g 포함)의 모든 함수들은 O(g)에 해당한다.

예)

\(O(n^{2})\) ∌ \(2n^{3} + 3n^{2} - 25\)

\(2n^{3} + 3n^{2} - 25\)은 g(n) = \(n^{2}\)보다 증가율이 더 빠른 함수이므로 \(O(n^{2})\)이 아니다.

\(O(n^{2}) \ni 10n^{2} + 3n - 25\)

\(10n^{2} + 3n - 25\)은 g(n) = \(n^{2}\)과 증가율이 같은 함수이므로 \(O(n^{2})\)이 맞다.

\(O(n^{2}) \ni 10nlogn + 5n\)

\(10nlogn + 5n\)은 g(n) = \(n^{2}\)보다 증가율이 더 느린 함수이므로 \(O(n^{2})\)이 맞다.