한빛출판네트워크

저자: 김대곤

* 알고리즘에 발가락 담그기
* 탐욕 알고리즘(Greedy Algorithm)
* 동적 프로그래밍(Dynamic Programming) – 고급 설계 기법인가?
* Induction과 병합 정렬(Merge Sort) 알고리즘
* 거짓말 같은 Induction

알고리즘의 계산복잡도를 구한다는 것은 각 단위 문장이 실행되는 수를 입력값의 크기에 비례하는 함수로 표현하는 것을 말한다. 여기에서 등장하는 단위 문장이란 대입문장, 사칙연산 또는 수의 비교와 같은 것으로 컴퓨터 상에서 일정한(Constant) 시간이 소요된다고 생각되는 문장을 말한다. 예를 들어, 주어진 정수 N 개의 수의 합을 구하는 알고리즘을 생각해 보자.

GETSUM(A, N)
1.  sum <- 0
2.  FOR i = 1 … N
3.     sum <- sum + A[i]
4.  RETURN sum

1번과 4번 문장은 단 한 번 실행되고, 2번 문장은 N(또는 N+1)번 실행되고, 3번 문장은 N번 실행된다. 실제 컴퓨터 상에서 각 문장이 소요되는 시간이 다르므로, 정확하게 표현하면, 이 알고리즘의 계산복잡도는 C1 + C2*N + C3*N + C4 가 된다. 여기서 C1은 1번 문장이 실행되는데 걸리는 시간을 말한다. 하지만 일반적으로 위의 알고리즘은 Θ(N)이라고 한다.(Θ는 그리스 문자로 데타(THETA)로 발음된다.)

여기서 몇 가지 가정들을 살펴보자. 즉 각 상수들이 무시되었다. 간단하게 말해서 모든 상수들이 전부 1로 치환되었다고 생각하면 된다. 그러면 2N+2 인데, 왜 Θ(N)이라고 부르는가? 그 이유는 Θ의 수학적 정의에서 찾을 수 있다. F(n) = Θ(G(n))는 다음과 같이 정의된다.

충분히 큰 n에 대해서, 다음을 만족하는 0보다 큰 두 개의 상수 D1, D2가 존재한다.
D1 * G(n) <= F(n) <= D2 * G(n)

위의 예제와 관련해서 생각해 보면, N이 3보다 큰 경우에, F(N)=2N+2 은 3 * N 보다 작고 N 보다는 크다. 여기서 G(N)은 N 이고, D1와 D2는 각각 1과 3 이다. 위의 알고리즘은 Θ(100*N)이라고 부를 수도 있다. 단지 가장 간단한 함수로 표현된 것 뿐이다.

알고리즘의 계산복잡도를 결정하는 요소는 크게 네 가지로 구분할 수 있다.

- 단순 반복문(루프)
- 재귀호출
- 테스트 문(IF, WHILE, 또는 UNTIL)
- 함수의 호출

위의 예제에서는 반복문만 등장하였다. 반복문의 계산복잡도는 반복되는 횟수를 통해 쉽게 구할 수 있고, 입력값의 수에 대해 항상 일정하고, 입력되는 값에 좌우되지 않는다. 반면에 재귀호출이나 테스트 문의 경우에는 새로운 문제를 야기시키는데, 입력되는 값이 따라 계산 복잡도가 바뀌는 것이다. 일반적으로 세 가지 경우를 생각한다. Best Case, Average Case, Worst Case가 그것이다. 삽입 정렬(Insert sort)와 빠른 정렬(Quick sort)를 통해서 자세하게 살펴보도록 하자.

테스트 문(IF, WHILE, 또는 UNTIL)

INSERTION_SORT(A, N)
1.  FOR j = 2 … N
2.      x <- A[j]
3.      i <- j-1
4.      WHILE ( i > 0 AND A[i] > x )
5.          A[i+1] = A[i]
6.          i <- i-1
7.      A[i+1] <- x

1번 문장은 N-1(또는 N)번 수행되고, 2번과 3번 문장은 N-1번 수행된다. 나머지 4,5,6번 문장이 수행되는 정확한 횟수는 알 수가 없고, 1번에서 j-1번 실행될 수 있다는 사실만 알 수 있다. 만약 모든 경우에 1번 실행된다면, INSERTION_SORT는 Θ(N)이라고 할 수 있다. 만약 항상 j-1번 수행된다면, 4번 문장의 경우 1+2+…+N 실행되고 INSERTION_SORT는 Θ(N*N)이라고 할 수 있다. 각 실행되는 횟수를 반으로 줄여서 평균을 만들어도 INSERTION_SORT는 Θ(N*N)이다. 이렇게 생각해 보자. 4,5,6번이 실행되는 시간을 반으로 줄여보자. 그리면 항상 j-1번 수행되는 경우와 수행시간이 같게 된다. Θ에서는 상수는 무시되므로 반으로 줄어든 상수를 무시하면, 여전히 Θ(N*N)가 된다.

위에서 본 세 가지 경우가 각각 Base Case, Worst Case, Average Case이다. 일반적으로 Worst Case를 기준으로 알고리즘의 계산복잡도를 말하는데. 위에서 본 바와 같이 Average Case는 Worst Case와 Θ로 표현했을 때 함수가 같은 경우가 많기 때문이다. 때로는 asymptotic 함수가 같다고 표현되기도 한다. INSERTION_SORT의 경우, Best Case는 Θ (N), Worst Case와 Average Case는 Θ(N*N)의 계산복잡도를 가지게 된다. 즉 어느 것도 정확한 계산복잡도라고 할 수 없게 되는데, 이러한 문제를 해결해 주는 것이 O(Big O)이다. O(G(N))는 G(N)보다 같거나 느리다는 표현이다. O(N*N)는 N*N보다 천천히 증가하는 모든 함수를 포함하게 된다. N도 포함 되고, N*N도 포함된다. 그래서 INSERTION_SORT의 계산복잡도는 O(N*N)이 된다. 사족을 붙이자면, INSERTION_SORT의 계산복잡도를 O(N*N*N)로 표현해도 수학적으로 틀린 표현은 아니다. 그러나 이런 경우를 계산복잡도의 한계가 Tight하지 않다고 한다.

재귀호출

이제는 Quick 정렬을 통해 계산복잡도가 재귀함수로 표현되는 경우를 살펴보도록 하자. 또한 재귀호출이 어떻게 계산복잡도를 바꿀 수 있는지 더불어 살펴보도록 하자.

먼저 Quick 정렬 알고리즘을 살펴보자. Quick 정렬은 주어진 수의 배열에서 하나의 수를 정하여 전체 배열이 정렬되었을 때 그 수의 위치를 찾아서 그 수를 그 자리에 옮기고, 그 위치를 기준으로 작은 수는 좌편에 큰 수는 우편에 오도록 한다. 나누어진 두 개의 배열은 아무런 성질을 가지고 있지 않다. 즉 임의의 배열이라고 할 수 있다. 나누어진 두 개의 배열에 대해서는 동일한 Quick 정렬을 호출하여 각각 정렬한다. 주어진 배열에서 하나의 수를 정하여 그 수를 기준으로 두 개의 배열로 나누는 과정은 주어진 배열의 크기에 비례한다.

처음 배열의 크기를 N이라고 하자.
(1) 선택된 수의 정렬 위치가 주어진 배열의 가운데라고 가정해 보자. 처음 수행되고 난 후에는 N/2의 크기의 두 개의 배열이 남게 된다. 즉 전체 과정은 T(N)은 Θ(N) 후에 2T(N/2)가 된다. T(N) = 2 T(N/2) + Θ(N) 이라는 계산복잡도를 가지게 된다.

(2) 선택된 수의 위치가 첫번째라고 가정해 보자. 두 개의 배열이 아닌 하나의 배열만 남게 되고, 그 배열의 크기는 N-1이 된다. 즉 T(N)=T(n-1) + Θ(N)

위에서 보는 바와 같이 재귀호출의 경우, 계산복잡도는 재귀함수로 표현되고, 그 재귀함수를 찾는 것은 어렵지 않다. 그러나, 재귀함수로 표현된 계산복잡도는 비교하기 힘들다. 그래서 재귀함수를 풀어서 비교하는데, 재귀함수를 일반 함수로 바꾸는 일이 그렇게 쉽지만은 않다. 이 문제는 다음 기사로 미루어 두자.

단도직입적으로 말해서, (1)의 계산복잡도는 Θ(N*log(N)) 이고, (2)의 경우는 Θ(N*N)이다.

함수
함수의 경우는 그 함수의 계산복잡도를 대입하면 된다. 예를 들면, 주어진 알고리즘에서 계산복잡도가 Θ(N)인 함수가 N번 수행되면 계산복잡도는 Θ(N*N)에 나머지 부분의 계산복잡도를 합한 것이 된다. 삽입정렬에서 WHILE 블럭을 함수로 대치했다고 생각해 보면, 더 좀 이해가 잘 되리라 생각된다.

그러면, 도대체 알고리즘의 계산복잡도는 왜 구하는 것일까? 이유는 매우 간단하다. 계산복잡도가 중요하기 때문이다. 앞에서 예를 들었던 삽입정렬은 Θ(N*N)의 계산복잡도를 Quick 정렬은 Θ(N*log(N))을 가지고 있다. 만약 두 개의 알고리즘을 서로 다른 컴퓨터에서 실행한다고 가정해 보자. 하나는 10년도 지난 구식, 속도 286 MHz의 컴퓨터이고, 다른 하나는 미래에 개발될 286 GHz 컴퓨터이다. 속도가 100 배 정도 차이가 난다. 즉 각 문장의 소요 시간이 100 배 정도 빠르다. 정리하면, 첫 번째 경우는 N*log(N) 초 걸리고, 두 번째 경우는 (1/100)*N * (1/100)*N 초 걸린다. 입력되는 배열에 크기에 따른 실행시간을 도표로 만들면 다음과 같다.



처음에는 최신형 컴퓨터가 엄청나게 빠르게 보여도, 입력되는 배열에 크기에 따라 역전되며,그 속도의 차이도 매우 빠르게 늘어나게 된다. 입력되는 배열이 큰 경우에는 10년 훨씬 이상의 컴퓨터 성능의 발전으로도 할 수 없는 계산 속도의 향상을 계산복잡도가 낮은 알고리즘은 지금도 할 수 있다. 이런 즉면에서 알고리즘은 강력한 기술(Technology)라고 말하며, 계산복잡도는 알고리즘을 효율성이라는 측면에서 그 차이를 분명하게 보여주는 지표가 된다.

알고리즘의 계산복잡도가 가진 또 다른 아름다움은 그 단순함에 있다. 즉 Θ나 big O 표현이 가진 단순화 시키는 힘이다. 만약 각 문장별 수행시간을 계산하고, 수행되는 정확한 횟수를 기반으로 알고리즘을 비교한다면 어쩌면 알고리즘은 서로 비교되지 않은 채 남아 있었을지도 모른다. 당신은 아는가, log(1*2*…*N) = Θ(N*log(N)) 이라는 사실을?