[이산수학]시간 복잡도와 공간 복잡도
시간 복잡도란 컴퓨터 프로그램의 입력값과 계산 수행 시간의 관계를 나타내는 척도이다.
이와 비슷하게 공간 복잡도란 프로그램의 입력값과 메모리 공간의 관계를 나타내는 척도이다.
두 개념 모두 점근 표기법이란 것을 통해서 나타낸다.
점근 표기법은 함수의 증감 양상을 나타내는 것이다. (이번 글은 기초적인 극한 개념이 필요합니다.)
점근 표기법은 여러가지가 있으며 다음과 같이 정의된다.
함수 $f:X\rightarrow Y$에 대해서 ($X$와 $Y$는 보통 실수 또는 자연수이다.)
$$f= \mathcal{o}(g)\iff \lim_{x\to \infty} \frac{f(x)}{g(x)}=0$$
$$f= \mathcal{O}(g)\iff \limsup \frac{f}{g}<\infty$$
$$f\sim g\iff \lim_{x\to \infty}\frac{f(x)}{g(x)}=1$$
$$f= \Omega(g)\iff \liminf \frac{f}{g}>0$$
$$f= \omega(g)\iff \lim_{x\to \infty}\frac{f(x)}{g(x)}=\infty$$
$$f= \Theta(g)\iff f\in \mathcal{O}(g)\wedge f\in \Omega(g)$$
(간혹, $f\in \mathcal{O}(g)$로 표현하는 경우도 있다.)
위 정의를 보면 알 수 있겠지만 시간이나 공간의 복잡도가 낮은 경우 더 효율적인 알고리즘이다. 주로 시간 복잡도를 다루며, $\mathcal{O}(g)$표기법을 쓴다.
시간 복잡도 $\mathcal{O}(1)$
다음은 시간 복잡도가 $\mathcal{O}(1)$인 알고리즘의 예시이다.
procedure test$(n:integer)$
for $i := 1$ to 100
$\quad$$n :=n+1$
return $n$
정수 $n$이 아무리 커져도 반복문은 100번, 초기화 연산자의 연산 횟수 또한 변하지 않는다. 따라서 시간 복잡도는 $test\in \mathcal{O}(1)$이다.
시간 복잡도 $\mathcal{O}(n)$
다음은 시간 복잡도 $\mathcal{O}(n)$의 예시이다.
procedure test$(n:\mathrm{natural\ number})$
$s := 0$
for $i := 1$ to $n$
$\quad$$s := s+i$
return $s$
1부터 $n$까지의 자연수들의 합을 구하는 알고리즘이다. 입력값 $n$에 따라서 반복문이 $n$회 반복하기 때문에 시간 복잡도는 $test\in \mathcal{O}(n)$이다. 이외에도 저번에 다룬 선형 탐색 알고리즘 또한 $\mathcal{O}(n)$이다.
시간 복잡도 $\mathcal{O}(n^2)$
다음은 시간 복잡도가 $\mathcal{O}(n^2)$인 알고리즘이다.
procedure test$(M:\mathfrak{Mat}_{n\times n}(\mathbb R), t:\mathrm{real\ number})$
for $i := 1$ to $n$
$\quad$for $j:=1$ to $n$
$\quad$$\quad$if $M_{ij}=t$ then return $(i,j)$
return -1
행렬은 2차원 배열이라고 생각하면 된다. 이외에도 저번에 다룬 정렬 알고리즘들 또한 $\mathcal{O}(n^2)$의 시간 복잡도를 갖는다.
시간 복잡도 $\mathcal{O}(nmk)$
다음은 시간 복잡도가 $\mathcal{O}(nmk)$인 알고리즘이다.
procedure matrix product$(A:\mathfrak{Mat}_{n\times k}(\mathbb R),\ B:\mathfrak{Mat}_{k\times m}(\mathbb R))$
for $i:=1$ to $n$
$\quad$for $j:=1$ to $m$
$\quad$$\quad$$c_{ij}:=\Sigma_{x=1}^{k}a_{ix}b_{xj}$
return $(c_{ij}) \in \mathfrak{Mat}_{n\times m}(\mathbb{R})$
또는
procedure matrix product$(A:\mathfrak{Mat}_{n\times k}(\mathbb R),\ B:\mathfrak{Mat}_{k\times m}(\mathbb R))$
$C:\mathfrak{Mat}_{n\times m}(\mathbb{R})$
for $i:=1$ to $n$
$\quad$for $j:=1$ to $m$
$\quad$$\quad$$s:=0$
$\quad$$\quad$for $x:=1$ to $k$
$\quad$$\quad$$\quad$$s:=s+a_{ix}b_{xj}$
$\quad$$\quad$$c_{ij}=s$
return $C$
시간 복잡도 $\mathcal{O}(\log n)$
저번에 다룬 이진 탐색 알고리즘은 해당 시간 복잡도를 갖는다. 참고로 컴퓨터 과학에서는 로그의 밑을 생략하는 경우, 로그의 밑은 2이다.
procedure binary search$(x:\mathrm{integer},\ \vec v:n-\mathrm{tuple})$
$i:=1$
$j:=n$
while $i < j$
$\quad$$m:=\lfloor \frac{(i+j)}{2}\rfloor$
$\quad$if $x>v_m$ then $i:=m+1$
$\quad$else $j:=m$
if $x=v_i$ then $location:=i$
else $location:=0$
return $location$
시간 복잡도 $\mathcal{O}(2^n)$
대표적인 예로 피보나치 수열이 있다. 보통 재귀 함수로 구현한다.
procedure fibonacci$(n:\mathrm{natural\ number})$
if $n=1\vee n=2$ then return 1
else return fibonacci$(n-1)+$fibonacci$(n-2)$
재귀식은 다음과 같다.
$$ F_1=F_2=1\\ F_n=F_{n-1}+F_{n-2} $$
마스터 정리
마스터 정리는 재귀 함수의 시간 복잡도를 쉽게 구할 수 있게 해준다. 내용은 다음과 같다.
$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$
여기서 $a$는 재귀 호출의 개수, $b$는 입력의 크기를 나누는 비율, $f(n)$은 재귀 호출이 아닌 부분의 연산량이다. 이러한 점화식의 복잡도는 다음과 같다.
$$ T(n)=\begin{cases} \mathcal{O}(n^{\log_ba}) & f(n)=\mathcal{O}(n^c)\wedge c<\log_ba \\ \mathcal{O}(n^{\log_ba}\log n) & f(n)=\mathcal{O}(n^c)\wedge c=\log_ba \\ \mathcal{O}(f(n)) & f(n)=\mathcal{O}(n^c)\wedge c>\log_ba \end{cases} $$
예를 들어 다음과 같은 함수를 정의하자.
procedure merge_sort$(i:\mathrm{integer},\ j:\mathrm{integer})$
$m:=\lfloor \frac{i+j}{2}\rfloor$
if $i<j$ then
$\quad$merge_sort$(i,\ m)$
$\quad$merge_sort$(m,\ j)$
$\quad$merge$(i,\ m,\ j)$
이 함수는 재귀함수이며, 복잡도는 다음과 같이 구해진다. 우선 재귀 호출 부분이 2개이다. 따라서 $a$는 2이고, 입력값이 반씩 줄어들기 때문에 $b$는 2이다. 그리고 $f(n)$은 merge$(i,\ m,\ j)$에 해당하며, $\mathcal{O}(n)$이다. 따라서 재귀식은 다음과 같다.
$$T(n)=2T\left(\frac{n}{2}\right)+n$$
$1=\log_2 2$이므로 이 함수의 시간 복잡도는 $\mathcal{O}(n\log n)$이다.