k-way Merge Sort(합병 정렬)의 시간복잡도 계산하기

이번 포스트에서는 분할 정복 알고리즘(Divide and Conquer Algorithm)중 하나인 합병 정렬(Merge Sort)의 개념과 시간 복잡도 계산 과정 등에 대해 정리하고자 한다. 여기서 분할 정복이란 입력 사례를 두 개 이상의 작은 입력사례로 바로 답을 구할 수 있을 만큼 충분히 작아질 때 까지 분할하고, 작은 입력사례에 대해 각각 답을 구한 후(정복 한 후), 각각을 결합하여 문제를 해결하는 방법이다. 

 

1. 2-way 합병 정렬(2-way Merge Sort)

앞에서 설명한 것과 같이 분할 정복 알고리즘은 분할(Divide), 정복(Conquer), 결합(Combine) 크게 세가지 과정으로 이루어 진다, 가장 일반적인 합병 정렬 방식은 분할 단계에서 입력 사례를 두 개의 작은 입력 사례로 분할하는 2-way 합병 정렬이다. 2-way 합병 정렬은 다음과 같은 세 단계로 진행된다.

 

Step1. 분할(Divide): 배열을 반으로 분할한다. 분할한 배열의 원소는 각각 n/2이다.

Step2. 정복(Conquer): 분할한 배열을 각각 따로 정렬한다. 분할한 배열에 원소의 크기가 2개 이상이면 순환 호출을 이용하여 다시 분할 정복 알고리즘을 적용한다.

Step3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열로 합병하여 정렬한다.

 

 

두 개의 정렬된 배열을 합병(merge)하는 과정은 아래 표와 같으며 최악의 경우 (전체 배열 크기-1)번의 비교 연산으로 두 개의 정렬된 배열의 합병이 가능하다.

 

2-way 합병 정렬의 진행 과정에 대해 알아 보았으니 시간 복잡도를 계산해 보자.

다음과 같은 수식에 의해 2-way 합병 정렬의 시간복잡도는 

 이다. 합병 정렬은 데이터 분포에 영향을 적게받아 안정적이고 빠른 정렬 방법 중 하나이다.

 

2. k-way 합병 정렬(k-way Merge Sort)

k-way 합병 정렬은 앞에서 설명한 2-way 합병 정렬을 일반화 한것으로 분할 단계에서 배열을 2개가 아닌 k개의 부분 배열로 분할하여 정렬을 진행하는 방식이다. 이 때 합병 단계에서 k개의 부분배열을 하나의 배열로 합병하기 위해서는 

 

첫번째 부분배열과 두번째 부분배열을 합병, 합병한 배열과 세번째 부분배열을 합병, . . . , 합병한 배열과 k번째 부분배열을 합병 

 

하는 과정을 거쳐야 한다. 이때 전체 배열의 크기가 n, 부분 배열의 크기가 각각 n/k 라면,

첫번째 부분배열과 두번째 부분배열을 합병하는 과정에서 최악의 경우 (2n/k-1)번의 비교연산이, 합병한 배열과 세번째 부분배열을 합병하는 과정에서는 최악의 경우 (3n/k-1)번의 비교연산이, . . . , 합병한 배열과 k번째 부분배열을 합병하는 과정에서는 최악의 경우 (kn/k-1)번의 비교연산이 필요하다. 이를 모두 더하면, 

번의 비교연산으로 k 개의 정렬된 배열의 합병이 가능하다.

 

그렇다면, k-way 합병 정렬의 시간 복잡도를 계산해 보자.

다음과 같은 수식에 의해 k-way 합병 정렬의 시간복잡도는 

 이다. 로그의 밑은 시간 복잡도에 영향을 미치지 않으므로 k값에 관계없이 시간 복잡도는 동일하다. (로그의 밑이 시간복잡도에 영향을 미치지 않는 이유는 다음 링크를 참고: https://www.quora.com/Why-we-do-not-consider-base-of-log-in-time-complexity). 하지만, 실제 소요 시간은 오히려 k가 커질수록 길 수도 있는데, 이는 부분 배열의 개수가 많을 수록 순환 호출의 깊이는 감소 하지만, 이들을 합병하는 과정에서 비교연산이 더 많이 필요하기 때문이다.

 

이번 포스트는 알고리즘 강의 시간에 교수님께서 생각해 보라고 하셨던 내용에 대해 정리한 것이다. 어떠한 검증과정을 거치지 않았기 때문에 다른 포스트보다 내용상 비약이나 오류가 존재 할 가능성이 있다. 혹시 잘못된 내용이 있으면 종류를 막론하고 피드백을 부탁한다.