📂알고리즘

시간복잡도와 공간복잡도

정의

주어진 문제를 풀 때의 걸리는 시간을 시간복잡도^{time Complexity}, 메모리 소요를 공간복잡도^{space Complexity}라고 한다.

예시

점근적 표기법은 이들을 표현하는데에 굉장히 유용한 수단이 된다. 시간복잡도에 대한 예시를 살펴보자.

상수 시간 $O(1)$

$n$ 에 관계없이 끝낼 수 있는 알고리즘으로, 사실상 시간이 걸리지 않는 것이다. 가령 $\mathbf{x} = [4,3,8,-1,-9,0,5,7,2,6]$ 에서 세번째 원소를 찾는 알고리즘은 $\mathbf{x}$ 가 어떻게 생겨먹었는지에 관심이 없고, 그냥 $8$ 을 반환하면 된다.

선형 시간 $O(n)$

$n$ 에 비례하는 시간이 걸린다. 가령 $\mathbf{x} = [4,3,8,-1,-9,0,5,7,2,6]$ 의 최대값을 찾는 알고리즘은 $8$ 을 세번만에 찾아낼 수 있지만, 그것이 진짜 최대값임을 보장하기 위해 나머지 원소도 모두 체크해야한다. 표현이 이러니까 조금 안 좋은 것 같지만, 사실 선형시간 정도면 꽤 빠른 알고리즘이라고 한다.

이차 시간 $O(n^2)$

$n^2$ 에 비례하는 시간이 걸린다. 가령 $\mathbf{x} = [4,3,8,-1,-9,0,5,7,2,6]$ 을 크기 순으로 정렬한다고 하면 최대값을 한 번 찾아 맨 끝에 두고, 그 최대값을 뺀 배열에서 또 한 번 최대값을 찾고를 반복하면 된다. 최대값을 한 번 찾을 때마다 $n, n-1, \cdots , 1$ 번의 시간이 걸리므로 그 합은 등차수열의 합 공식에 따라 $\displaystyle \sum_{k=1}^{n} k = {{ n (n+1)} \over {2}} = O(n^2)$ 이 된다. 이보다 현명한 방법이 있을 것 같지만, 이보다 미련한 방법은 고민할 필요가 없다.

삼차 시간 $O(n^3)$

$n^3$ 에 비례하는 시간이 걸린다. 예로써 $n=2^{k}$ 일 때 $n \times n$ 행렬의 곱셈을 생각해볼 수 있는데, $A, B \in \mathbb{R}^{n \times n}$ 을 곱한 $C = AB$ 를 구한다고 생각해보자. 그러면 조던 블록Jordan Block 행렬 표현을 사용해 다음과 같은 8개의 ${{n} \over {2}} \times {{n} \over {2}}$ 행렬의 곱을 구해서 계산할 수 있다. $$AB= \begin{bmatrix} A_{1} & A_{2} \\ A_{3} & A_{4} \end{bmatrix} \begin{bmatrix} B_{1} & B_{2} \\ B_{3} & B_{4} \end{bmatrix} = \begin{bmatrix} C_{1} & C_{2} \\ C_{3} & C_{4} \end{bmatrix} = C$$

$$C_{1} = A_{1}B_{1} + A_{2} B_{3}$$

$$C_{2} = A_{1}B_{2} + A_{2} B_{4}$$

$$C_{3} = A_{3}B_{1} + A_{4} B_{3}$$

$$C_{4} = A_{3}B_{2} + A_{4} B_{4}$$ 이 계산을 계속 반복하면 되는데, 한번 계산하는데 걸리는 시간이 $T(n)$ 이고 반복 외의 수행시간을 $c$ 라고 하면 $\displaystyle T(n) = 8 T \left( {{n} \over {2}} \right) + c$ 이므로 $$\begin{align*} T(n) =& 8 T \left( {{n} \over {2}} \right) + c \\ =& 8 \left[ 8 T \left( {{n} \over {4}} \right) + c \right] + c \\ =& 8 \left[ 64 T \left( {{n} \over {8}} \right) + 8 c + c \right] + c \\ =& 8^3 T \left( {{n} \over {8}} \right) + (1+8+8^2)c \\ =& 8^3 T \left( {{n} \over {8}} \right) + {{8^3 - 1} \over {8 - 1}}c \\ & \vdots & \\ \approx& 8^{\log_{2} n} ( T(1) + c ) \\ =& n^{\log_{2} 8} ( T(1) + c ) \\ =& n^{3} ( T(1) + c ) \\ =& \Theta ( n^3 ) \end{align*}$$ 이기 때문이다. 행렬의 곱셈은 수학이 들어간 응용분야라면 거의 예외 없이, 그것도 굉장히 많이 한다. 그런데 $n^3$ 은 좀 크다. $n=100$ 만 되어도 무려 $n^3 = 10^6$ 이 된다. 과연 여기서 더 계산을 줄일 수 있을까? 애초에 쓸데 없는 계산을 하지 않는데 여기서 뭘 어떻게 더 줄일 게 없어보인다. 하지만 슈트라센 알고리즘이라는 놀라운 방법을 사용하면 이걸 더 줄일 수 있다. 이것이 알고리즘의 묘미다.

로그 시간 $O \left( \log (n) \right)$

엄청 빠르다는 의미다. 가령 정렬 된 배열 $\text{sort} (\mathbf{x}) = [-9,-1,0,2,3,4,5,6,7,8]$ 에서 $0$ 의 위치를 찾는 문제가 있다고 하자. 간단하게 떠올릴 수 있는 방법은 한 가운데의 원소 하나를 골라 $0$ 보다 큰지 작은지 확인해서 $0$ 보다 크면 오른쪽을 버리고, 작으면 왼쪽을 버리는 식으로 배열을 줄여나가 찾는 것이다. 이를 이진 탐색^{binary search}이라고 한다. 한번 계산하는데 걸리는 시간이 $T(n)$ 이고 비교하는데 걸리는 시간을 $c$ 라고 하면 $\displaystyle T(n) = T \left( {{n} \over {2}} \right) + c$ 이므로 $$\begin{align*} T(n) =& T \left( {{n} \over {2}} \right) + c \\ =& \left[ T \left( {{n} \over {4}} \right) + c \right] + c \\ =& T \left( {{n} \over {4}} \right) + 2 c \\ =& T \left( {{n} \over {8}} \right) + 3 c \\ & \vdots & \\ \approx& T \left( 1 \right) + c \log_{2} n \\ =& O \left( \log_{2} (n) \right) \end{align*}$$ 이기 때문이다. 로그 밑변환 공식에 따라 $O( \log (n)))$ 이 된다고 해도 좋지만, 원래 컴퓨터 공학에서 로그에 별다른 말이 없다면 밑은 보통 $e = 2.7182…$ 가 아니라 $2$ 로 두기 때문에 표현에 신경쓸 필요는 없다.

지수 시간 $O(2^n)$

엄청 오래 걸린다는 의미다. 재귀함수를 사용해서 피보나치 수열을 구하는 경우 매우 비효율적인데, 한 번 계산이 $n$ 번째 피보나치 수 $a_{n}$ 을 구하기 위한 시간이 $T(n)$ 이고 앞 두 항을 더하는데 걸리는 시간을 $c$ 라고 하면 $T(n) = T(n-1) + T(n-2) + c$ 이므로 황금비 $\phi = 1.618…$ 에 대해서 $$\begin{align*} T(n) =& T(n-1) + T(n-2) + c \\ =& [ T(n-2) + T(n-3) + c ] + T(n-2) + c \\ =& 2 T(n-2) + T(n-3) + (1+1) c \\ =& 3 T(n-3) + 2 T(n-4) + (1+1+2) c \\ =& 5 T(n-4) + 3 T(n-5) + (1+1+2 + 3) c \\ =& 8 T(n-6) + 5 T(n-4) + (1+1+2+3+5) c \\ & \vdots & \\ =& c \sum_{k=1}^{n} a_{n} \\ \approx& {{\phi^{n-1}-1} \over {\phi-1}} c \\ =& \Omega ( \phi^n ) \end{align*}$$ 이기 때문이다. 마지막 부분은 $\displaystyle \phi \approx {{a_{n}} \over {a_{n-1}}}$ 이므로 등비수열의 합 공식을 이용해 근사시킨 것이다. 이런 알고리즘은 현실적으로 사용하는 게 불가능하므로 동적 프로그래밍과 같은 해법을 찾아보거나 거꾸로 이러한 시간 복잡도를 가진다는 점을 이용하면 암호에 응용할 수 있기도 하다.