16. 점근법 표현들 (Asymptotic Notations)

어떤 값이 어떤 값과 근사함을 나타내는 표현들을 알아보자.

Tilde

tilde는 $\sim$으로 나타낸다. 의미는 아래와 같다.

$$ f(x) \sim g(x) \text{ if } \lim_{x\rightarrow \infty} \frac{f(x)}{g(x)} = 1 $$

Big Oh

Big Oh 표기는 $O(g(x))$와 같이 나타내며, 의미는 아래와 같다.

$$f(x) = O(g(x)) \text{ if } \lim_{x\rightarrow \infty} |\frac{f(x)}{g(x)} | < \infty $$

Big Oh 표기법에서, $f(x)$는 $g(x)$보다 작거나 같다. 즉, Big Oh 표기법은 상한을 이용한다.

Big Oh 표기법에 사용되는 $g(x)$는 항상 최악의 경우(값이 가장 커지는)를 가정하기 때문에, 알고리즘의 속도 표기에 자주 사용된다.

$n\times n$ 행렬을 곱하는데 걸리는 시간 $T(n) = O(n^3)$이다.

점근 표현의 올바른 사용

Big Oh는 두 함수의 시간 비교에 사용된다. 그러므로 아래와 같은 활용은 옳지 않다.

$$ ax^2 = bx + O(g(x))$$

$g(x)$와 다른 함수를 비교하기 때문에, 아래와 같이 표기하는 것이 좋다.

$$ ax^2 - bx = O(g(x))$$

tilde 또한 값의 근사를 나타내기 때문에, 아래와 같이 나타내는 것이 좋다.

$$ ax^2 - bx \sim \delta $$

Big Oh는 상한을 표기하기 위한 것이므로, 아래와 같은 활용은 적절하지 않다.

$$ f(x) \geq O(g(x))$$

Big Omega

Big Omega는 Big Oh와 반대로 하한을 나타낸다.

$$f(x) = \Omega (g(x)) \text{ if } \lim_{x\rightarrow \infty} |\frac{f(x)}{g(x)}| > 0$$

$$f(x) = O(g(x)) \iff g(x) = \Omega(f(x)) $$

Theta

Theta는 Big Omega와 비슷하나, 조건이 하나 더 붙는다.

$$ f(x) = \theta (g(x)) \text{ if } 0 < \lim_{x\rightarrow \infty} |\frac{f(x)}{g(x)} < \infty$$

예를들어, $10x^3 - 20x + 1 = \theta (x^3)$이다.

$T(n) = \theta(n^2)$는 $T$의 상한과 하한 모두가 $n$에 대해 2차로 증가한다는 것이다.

정리

$O: \leq$ (상한)

$\Omega : \geq$ (하한)

$\theta : =$

$o: <$ $(\lim_{x\rightarrow \infty} |\frac{f(x)}{g(x)}| = \not 0)$

$\omega: >$ $(\lim_{x\rightarrow \infty} |\frac{f(x)}{g(x)}| = \infty)$