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

점근적 표기법

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

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

 

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

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

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

 

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)$이 맞다.