병합정렬 시간복잡도 구하기

병합정렬^{Merge Sort}의 시간복잡도는 O(n·lg(n))를 가진다. 그런데 왜 그런가? 같은 분할정복 아이디어를 차용한, 1부터 N까지의 합을 구하는 알고리즘의 시간복잡도는 구하기 참 쉽다. 그러나, 병합정렬은 이보다는 어렵다. 그러니 한 번 계산해보자.

의사 코드

먼저, 병합정렬 알고리즘을 간단히 살펴보자. 아래 코드의 출처는 여기.

func mergesort( var a as array )
     if ( n == 1 ) return a

     var l1 as array = a[0] ... a[n/2]
     var l2 as array = a[n/2+1] ... a[n]

     l1 = mergesort( l1 )
     l2 = mergesort( l2 )

     return merge( l1, l2 )
end func

이 코드는 크게 3가지 부분으로 이뤄져 있다.

1. 분할: 4~5L
2. 정복: 7~8L
3. 병합: 10L (merge 내부 코드는 생략함)

각 단계의 수행 시간

3가지 단계의 수행 시간은 각각 얼마나 될까? (우리가 첫 번째 호출 스택에 있다고 가정해보자.)

1. 분할: 시작과 끝 인덱스의 중간 값을 찾는 나눗셈 1회 수행.
2. 정복: n/2 요소들에 대해, 현재 스택에서 수행하는 작업을 동일하게 수행함. x2
3. 병합: 비록 위 코드에서는 생략했지만, n번의 루프가 수행됨.

1번 단계와 3번 단계를 합치면, n + 1이 된다. 계산의 편의를 위해, 우리는 n + 1을 cn(c는 상수)으로 표현할 수 있다. 혹은 1을 무시하고 n으로 표현할 수도 있다. 우리가 왜 시간복잡도를 구하려 했는지 그 이유를 생각해 볼 때, 개인적으로는 후자를 선호한다. 수학에서 0.99999999999999…가 1과 같은 것도 같은 맥락 아닐까?

시간복잡도 트리

정복 단계가 하는 일은 재귀함수를 떠올리게 하는데, 이를 식으로 나타내면 아래와 같다.

T(n) = 2 · T(n/2) + n 혹은 T(n) = 2 · T(n/2) + cn

그리고 이를 트리 그림으로 표현해보자.

왼쪽의 숫자는 요소의 크기, 오른 쪽의 숫자는 분할과 병합에 소요되는 실행 시간이다. 첫 번째 깊이에서는 n번의 분할/병합 시간이 걸린다. 그리고 두 번째 깊이에서는 크기가 반으로 줄어 n/2 시간이 걸리지만, 총 2개의 태스크가 존재하므로, 전체 시간은 2·n/2 즉, n 시간이 소요된다. 세 번째 깊이에서는 물론, 1개 요소만이 남는 경우에도 마찬가지로 n 시간이 소요된다. 즉, 모든 트리 깊이에서 각각 n 시간이 걸린다.

계산은 끝났다.

참고로, Θ(n·lg(n))라고 표기해도 옳다.