Basics of Algorithm Analysis

 

* 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

Asymptotic Order of Growth

Polynomial-Time : input size N에 대해 running time이 $cN^d  steps$로 bound되는 constant c > 0, d > 0가 존재한다.

 

=> Running time이 polynomial할 때, 해당 알고리즘은 'efficient하다' 라고 한다.

 

 

 Asymptotic order의 정의들

Upper bounds

$T(n) = O(f(n))$ : if there exist constant $c>0$ and $n_0 \geq 0$ such that for all $n  \geq n_0$ we have $T(n) \leq c \cdot f(n)$

 

Lower bounds

$T(n) = \Omega(f(n))$ : if there exist constant $c>0$ and $n_0 \geq 0$ such that for all $n  \geq n_0$ we have $T(n) \geq c \cdot f(n)$

 

Tight bounds

$T(n) = \Theta(f(n))$ : if $T(n)$ is bot $O(f(n))$ and $\Omega(f(n))$

 

 

Transitivity

If $f = O(g)$ and $g = O(h)$ then $f = O(h)$

If $f = \Omega (g)$ and $g = \Omega (h) $ then $f = \Omega (h)$

If $f = \Theta (g)$ and $g = \Theta (h)$ then $f = \Theta (h)$

 

Additivity

If $f = O(h)$ and $g = O(h)$ then $f + g = O(h)$

If $f = \Omega (h)$  and $g = \Omega (h)$ then $f + g = \Omega (h)$

If $f = \Theta (h)$ and $g = \Theta (h) $ then $f + g = \Theta (h)$