알고리즘의 복잡도

Overview

하나의 문제를 해결하는 알고리즘은 여러가지가 존재할 수 있다. 우리는 이 중에서 어떤 알고리즘이 성능이 좋고 나쁜지 평가하는 기준이 필요하다. 알고리즘 성능의 평가기준은 크게 시간(Time)과 공간(Space)이 있다.

시간은 알고리즘이 답을 내기까지 걸리는 소요시간(수행시간), 공간은 알고리즘이 사용하는 (메모리)공간을 말한다. 아쉽게도 두 기준은 서로 상충하는 경우가 많다. 메모리 사용량을 늘려 속도를 높이거나, 속도를 희생하고 메모리 사용량을 줄이는 알고리즘도 있다. 보통은 속도를 중시하는 경우가 많다.

시간복잡도(Time Complexity)

시간복잡도는 일종의 함수로 입력크기(n)에 대해서 알고리즘이 결과를 내는데 필요한 연산의 수를 나타낸다.

예를 들어, 1부터 n까지 정렬된 리스트가 주어질때, 가장 큰 값을 리스트의 앞에서 순차적으로 찾는 알고리즘의 시간복잡도는 $f(n) = n$으로 이해할 수 있다. 여기서 알고리즘의 주요 연산은 리스트 한 원소와 현재까지 찾은 가장 큰 값을 비교하는 것이다.

동일한 문제를 푸는데 특정 알고리즘의 시간복잡도가 작다는 것은 입력의 크기($n$)가 커져도 알고리즘의 수행시간이 완만하게 증가한다는 의미이다. 반대로 크다는 것은 입력크기가 커질때 수행시간 더 급격히 증가한다는 의미다.

주의할 점은 특정 알고리즘의 시간 복잡도가 낮다고 해서 언제나 빠르게 동작하는 것은 아니다. 상황에 따라 입력의 크기가 작을 때는 시간 복잡도가 높은 알고리즘이 더 빠르게 동작하는 구간도 존재할 수 있다.

공간복잡도(Space Complexity)

공간복잡도는 일종의 함수로 입력크기(n)에 대해서 알고리즘이 결과를 내는데 필요한 공간의 크기를 나타낸다. 공간복잡도는 단지 관점이 다를뿐 큰 문맥은 시간복잡도와 동일하다.

특정 알고리즘이 공간복잡도가 작으면 입력의 크기($n$)가 커져도 메모리 사용량이 완만하게 증가한다는 의미다. 시간복잡도와 마찬가지로 공간복잡도가 낮다고 해서 가능한 모든 입력크기에 대해서 해당 알고리즘의 메모리 사용량이 적다고 단정하면 안된다. $n$에 따라 공간복잡도가 높은 알고리즘이 메모리를 더 적게 사용할 수도 있다.

입력형태에 따른 수행시간의 변화

사실 입력의 크기($n$)만이 수행시간을 결정하는 유일한 척도는 아니다. 입력크기 뿐만 아니라 입력의 형태도 수행시간에 지대한 영향을 미친다. (그 밖에 OS, CPU와 같은 환경에도 영향을 받는다.)

예를 들어, 배열에서 값을 원하는 값을 찾는 문제를 생각해보자. 입력의 형태에 따라 찾고자 하는 값이 맨 앞에 있을수도 있고, 맨 뒤에 있을 수도 있다. 알고리즘이 순차적으로 값을 찾는다면 최선의 경우 1번의 비교 연산 후에 답을 찾고, 최악에는 n번의 비교 후를 통해 답을 찾는다.이렇게 입력형태에 따라 수행시간이 크게 달라지기 때문에 최선, 최악의 경우를 모두 인식하는게 좋다.

때때로 단순히 최선, 최악의 관점으로 입력 형태에 따른 수행시간을 표현하기가 어려운 경우가 있다. 이럴 땐 모든 입력형태에 대해 소요시간의 평균을 구하여 수행시간을 나타내는데 사용한다.

예를 들어, 단순한 선형 탐색에서 특정 값을 찾는 경우, 값을 찾기 위한 평균 연산 수행 횟수는 아래와 같다.

$$N/2= (1 + 2 + ... + n) / n$$

---

점근적 시간 표기

시간복잡도는 알고리즘의 수행시간을 표기하는 방법이지만, 알고리즘을 완벽히 분석하고 그 정확한 연산 수를 계산하는 것은 보통 어려운 일이 아니다. 그리하여 수행시간에 큰 영향을 미치는 부분에 집중하는 표기법이 고안되었다. 그 중에 가장 대표적인 표기법이 바로 Big - O 표기법이다. 이러한 표기법에는 크게 세 가지 종류가 존재하며 하나씩 알아보자.

O 표기법(Big - O notation, Big O)

O 표기법은 알고리즘 수행시간의 표기법 중 하나로 복잡도의 상한(Upper Bound)을 나타낸다. 즉, O 표기법으로 표현된 알고리즘은 최악의 경우에도 제시한 복잡도 만큼의 성능은 보장한다는 의미다.

이제 수학적으로 O표기법을 이해해보자. $n$에 대한 복잡도 $f(n)$이 존재하고 $f(n)$에 대해 $f(n) = O(g(n))$라고 표기하는 것은 아래와 같은 의미이다.

적당히 큰 $n_0$ 보다 크거나 같은 모든 $n$에 대해서, $|f(n)| <= C * |g(n)|$을 만족하는 상수 C가 존재한다.

그림에서 볼 수 있듯이 $n_0$보다 큰 $n$에서 $f(n)$은 항상 $C*g(n)$보다 작다. 이렇게 $C*g(n)$는 복잡도 $f(n)$의 상한을 나타낸다.

예를 들어, 어떤 알고리즘이 $f(n) = O(n^3)$의 표기법으로 나타났다면 최악의 경우에도 $n^3$의 복잡도를 보장한다는 의미이다.

상수 $C$가 어떤 의미인지 이해가 어려울 수 있다. 예를 들어 알고리즘의 복잡도가 정확히 $f(n)=n^3$으로 주어지고 나아가 $g(n)=n^3$인 경우라면, $n^3 \le C*(n^3)$을 만족하는 C는 1이 존재하기 때문에 정의에 따라 $f(n)$을 $g(n)=n^3$으로 표현하는 것은 올바르게 상한을 나타낸다. 만약 $g(n)=n^2$이라면 $n^3 \le C * n^2$을 만족하는 $C$가 존재하지 않기 때문에 O표현이 불가하다.

Ω 표기법(small - O notation, Big Omega)

Ω표기법은 특정 알고리즘의 복잡도 하한(Lower Bound)을 나타내며, O 표기법과는 반대되는 개념이다. 즉, Ω표기법은 최선의 경우에 제시한 복잡도 만큼의 성능이 발생한다는 의미다.

$n$에 대한 복잡도$f(n)$이 존재하고 $f(n)$에 대해 $f(n)=Ω(g(n))$라고 표기하는 것은 아래와 같은 의미이다. 사실 앞서O 표기와 유일한 차이는 부등호의 방향이다.

적당히 큰 $n_0$ 보다 크거나 같은 모든 $n$에서, $|f(n)| \ge C * |g(n)|$을 만족하는 상수 C가 존재한다.

그림에서 볼 수 있듯이 $n_0$보다 큰 $n$에서 $f(n)$은 항상 $C*g(n)$보다 크다. 이렇게 $C*g(n)$은 복잡도 $f(n)$의 하한을 나타낸다.

예를 들어, 어떤 알고리즘의 복잡도가 $f(n)=Ω(n^2)$이라면 아무리 좋아도 $n^2$의 복잡도만큼의 성능까지 보일 수 있다는 뜻이다.

빅 세타 표기법(Big θ notation)

θ 표기법은 알고리즘 복잡도의 상한과 하한을 동시에 나타낸다. θ 표기가 된 알고리즘은 최선, 최악의 경우를 모두 통틀어서 표시한 복잡도만큼의 성능을 보인다.

임의의 복잡도$f(n)$이 존재하고 $f(n)=θ(g(n))$라고 표기하는 것은 아래 의미를 가진다.

적당히 큰 $n_0$ 보다 크거나 같은 모든 $n$에서, $C_1 |g(N)| \le |f(N)| \le C_2 * |g(N)|$을 만족하는 상수 $C_1$, $C_2$가 모두 존재한다.

$n_0$보다 큰 $n$에서 $f(n)$이 $C_1*g(n)$보다는 크지만 $C_2*g(n)$ 보다는 작다. 즉 위 그림은 복잡도 $f(n)$의 상한과 하한을 모두 보여주고 있다.

예를 들어, $f(n) = θ(n)$의 의미는 해당 알고리즘이 최악의 경우에도 $n$만큼의 성능을 나타내고 마찬가지로 최선의 경우에도 $n$만큼의 성능을 보인다는 것이다.

수행시간별 알고리즘의 종류

선형 시간 알고리즘

선형시간(linear) 알고리즘은 입력 크기 N(데이터의 크기)에 1:1로 비례하는 수행시간을 보이는 알고리즘을 말한다.

선형 이하 알고리즘

입력크기가 커지는 것에 비해 수행시간이 느리게 증가하는 알고리즘들을 선형이하 알고리즘(sublinear)이라 한다.

이미 날짜 별로 정렬된 사진첩이 주어졌을때, 특정 날짜의 사진을 찾는다고 하자. 시계열로 나열된 사진들의 중앙 날짜를 기준으로 사진이 과거에 해당하는지 미래에 해당하는지 확인 할때마다 찾아봐야할 사진의 수가 절반씩 줄어들기 때문에 $log N$번의 연산으로 사진을 찾을 수 있을 것이다. (사실 예로 들은 사진 찾기는 선형 이하 알고리즘의 대표 알고리즘인 이진 탐색(Binary Search)이다.)

다항 시간 알고리즘

변수 $N$, $N^2$ 그 외의 거듭제곱들의 선형 결합으로 이루어진 식들을 다항식이라고 부른다. 사실 다항 시간 알고리즘에 분류가 되는 알고리즘 간에도 엄청난 시간 차이가 날 수 있다. $N^2, N^3, ..., N^{100}$ 모두 같은 다항시간이다. 그런데도 이런 부류를 묶은 이유는 다항 시간 알고리즘보다 훨씬 더 오래 걸리는 알고리즘들이 있기 때문이다.

지수 시간 알고리즘

$2^N$ 과 같이 지수함수는 알고리즘의 전체 수행시간에 엄청난 영향을 미친다. $N$이 하나 증가할때마다 시간이 배로 증가하는 알고리즘을 지수시간(exponential time)에 동작한다고 한다.