대문자 O 표기법

대문자 O 표기법은 점근표기법의 일종으로 어떤 함수의 점근상한을 다른 함수로 표현하는 방법이다. 알고리즘의 시간복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다.

\frac{f(x)}{g(x)}

가

x\rightarrow\infty

일 때 상수로 수렴한다면, 즉

x>x_0

인 모든 실수 x에 대하여

|f(x)| \le \; M |g(x)|

가 성립하는

\;x_0, \;M>0

가 존재한다면

x\rightarrow \infty

일 때

f(x) \,

는

O(g(x)) \,

라고 한다. 또는,

f(x) = O(g(x))

라고 표기하기도 한다.

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

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

g(x) = x^4.  \,

이때 f(x)는 O(g(x)), 혹은 O(x⁴)이 된다. 증명은 다음과 같다.

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³ < x⁴와 같은 방법)

|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²)이므로 $O(x) = O(x^2)$ 로 표기할 수는 있지만, $O(x^2) = O(x)$ 와 같이 쓰는 것은 잘못된 표기이다.

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

표기법	설명	수학적 정의
$f(n) \in O(g(n))$	상한 점근	\lim_{n \to \infty} \left >\frac{f(n)}{g(n)}\right
$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
$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

정의에 따라,

f(x) = O(g(x))

와

g(x) = \Omega(f(x))

f(x) = o(g(x))

와

g(x) = \omega(f(x))

는 동치이다.

또한, $f(x) = O(g(x)), f(x) = \Omega(g(x))$ 와 $f(x) = \Theta(g(x))$ 도 동치 관계이다.

Gourt Home::Gourt :: 대문자 O 표기법