점근 표기법

위키백과 ― 우리 모두의 백과사전.

점근 표기법(asymptotic notation)은 어떤 함수의 증가율을 다른 함수와의 비교로 표현하는 방법이다. 알고리즘의 시간복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다.

점근 표기법에는 크게 다음과 같은 표기법이 있다.

대문자 O 표기법
소문자 o 표기법
대문자 오메가(Ω) 표기법
소문자 오메가(ω) 표기법
대문자 세타(Θ) 표기법

[편집] 대문자 O 표기법

[편집] 정의

$\frac{f(x)}{g(x)}$ 가 $\ x \rightarrow \infty$ 일 때의 극한값이 상수로 수렴한다면, 즉 $x > x 0$ 인 모든 실수 x에 대하여 $|f(x)| \le M |g(x)|$ 가 성립하는 $\; x_0,\ M>0$ 가 존재한다면 $\qquad x \rightarrow \infty$ 일 때 $f (x)$ 는 $O (g (x))$ 라고 한다. $f (x) = O (g (x))$ 라고 표기하기도 하며, 혹은 $O (g (x))$ 를 해당 $f (x)$ 의 집합으로 정의하기도 한다.

[편집] 예

두 다항식 $f, g$ 를 다음과 같이 정의한다.

f (x) = 6 x 4 - 2 x 3 + 5

g (x) = x 4

이때 $f (x) = O (g (x)) or O (x 4)$ 이 된다. 증명은 다음과 같다.

x > 1

일 때 $|6x^4 - 2x^3 + 5| \le 6x^4 + 2x^3 + 5$

$|6x^4 - 2x^3 + 5| \le 6x^4 + 2x^4 + 5x^4$ (

x 3 < x 4

와 같은 방법)

$|6x^4 - 2x^3 + 5| \le 13x^4$

$|6x^4 - 2x^3 + 5| \le 13 |x^4|$

[편집] 표기법 문제

$f (x) = O (g (x))$ 라는 표현에서, 등호는 원래의 등호와는 다른 의미를 가진다. 예를 들어,

어떤 함수가 $O (x)$ 이면 $O (x 2)$ 이므로 $O (x) = O (x 2)$ 로 표기할 수는 있지만, $O (x 2) = O (x)$ 와 같이 쓰는 것은 잘못된 표기이다. 이 때, 등호 표기는 일반적인 표기법과 다르게 사용된 기호의 남용으로 볼 수 있다.

이러한 문제를 방지하기 위해, $O (g (x))$ 를 원래 정의에서 해당하는 함수들의 집합으로 정의하는 경우도 많이 사용된다. 이러한 경우 $f(x) \in O(g(x))$ 과 같이 표기할 수 있고, 이것은 기호의 원래 정의와 잘 맞아 떨어진다.

[편집] 다른 표기법들

대문자 O 표기법과 비슷하게, 다음의 표기법들이 사용된다.

표기법	설명	수학적 정의
$f(n) \in O(g(n))$	상한 점근	$\lim_{n \to \infty} \left\|\frac{f(n)}{g(n)}\right\| < \infty$
$f(n) \in o(g(n))$		$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$
$f(n) \in \Omega(g(n))$	하한 점근	$\lim_{n \to \infty} \left\|\frac{f(n)}{g(n)}\right\| > 0$
$f(n) \in \omega(g(n))$		$\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$
$f(n) \in \Theta(g(n))$	상한/하한 점근	$0 < \lim_{n \to \infty} \left\|\frac{f(n)}{g(n)}\right\| < \infty$