Asymptotic Analysis

2020-1학기, 대학에서 ‘알고리즘’ 수업을 듣고 공부한 바를 정리한 글입니다. 지적은 언제나 환영입니다 :)

보통 우리는 어떤 알고리즘의 성능을 입력 데이터의 크기 $N$에 대한 함수로 표현한다. 이번 포스트에서는 알고리즘의 성능을 표기하는 여러 기법들에 대해 살펴본다 😎

$O$ Notaiton

For two functions $f(n)$ and $g(n)$, $f(n) = O(g(n))$,

iff there exist a constant $c > 0$ and $n_0 \ge 0$ s.t. for all $n \ge n_0$,

we have $f(n) \le c\cdot g(n)$

즉, $g(n)$ is an asymptotic upper bound of $f(n)$.

$\Omega$ Notaiton

For two functions $f(n)$ and $g(n)$, $f(n) = \Omega(g(n))$,

iff there exist a constant $c > 0$ and $n_0 \ge 0$ s.t. for all $n \ge n_0$,

we have $f(n) \ge c\cdot g(n)$

즉, $g(n)$ is an asymptotic lower bound of $f(n)$.

$\Theta$ Notaiton

$f(n)$ is $\Theta(g(n))$ iff $f(n) = \Omega(g(n)) = O(g(n))$.

즉, $g(n)$ is an asymptotic approximation of $f(n)$.

Examples

표기법에 익숙해지기 위해 몇가지 문제를 풀어보자.

Q1. Show that for all positive integer $n$,

\[7n^5 + 1024 n^4 + 3n (\log n)^{248} + 10 = O(n^5)\]

A1. 논리에 따라 조금만 끄적이면 금방 풀림.

Q2. (T/F) If $f(n) = \min \{ n, 10^6 \}$, then $O(1)$.

A2. E-Z

Q3. (T/F) If $f(n) = O(n)$, then $2^{f(n)} = O(2^n)$.

A3. E-Z

---

Other Asymptotic Bounds

Definition. little-o notation

For every $\epsilon > 0$,

there exists a constant $n_0$ s.t. $f(n) \le \epsilon \cdot g(n)$ for $n > n_0$,

then $f(n) = o(g(n))$.

Definition. little-omega notation

if $g(n) = o(f(n))$, then $f(n) = \omega(g(n))$.

Examples

이해를 돕기 위해 사례를 먼저 살펴보자.

[Trivial case]

• $f(n) \ne o(f(n))$

• $f(n) \ne \omega(f(n))$

• if $f(n) = o(g(n))$, then $f(n) = O(g(n))$. However, the converse is not true.

[Definition by Limitation]

If $\displaystyle\lim_{n\rightarrow\infty} \frac{f(n)}{g(n)} = 0$, then $f(n) = o(g(n))$.

Q4. (T/F) If $f(n) = 2^n$ and $g(n) = n^c$ for $c \in \mathbb{N}$, then $g(n) = o(f(n))$.

A4. E-Z. 앞에서 언급한 극한으로 정의한 little-o notation을 쓰면 바로 풀린다.

Q5. Show that for any fixed but arbitrarily small real number $c > 0$,

\[n \log n = o(n^{1+c})\]

A5. E-Z. 이것도 극한으로 정의한 버전을 쓰면 바로 풀림.

---

Exercises

Q. (T/F) $2^n = n^{\omega(1)}$.

A. E-Z. 식을 잘 정리한 후에, 극한으로 정의한 버전을 씀.

---

이번에 살펴본 <Asymptotic Analysis>는 알고리즘의 성능을 개략적으로 판단하는 지표다. 경우에 따라서는 알고리즘에 붙은 덧셈·곱셈의 상수텀 역시 중요하다.

그러나 <Asympototic Analysis>는 최악의 상황 아래서 알고리즘의 성능을 평가하기 때문에, 이것이 오히려 알고리즘의 실제 비용을 부풀리게 만들기도 한다. 이런 문제점을 개선한 것이 바로 <Amortized Analysis>이다. 고급 자료구조를 쓸때 <Amortized Analysis>가 자주 등장하기 때문에, 꼭 알아야 하는 기법 중 하나다.

👉 Amortized Analysis