병합 정렬 분석하기

$n$‍개의 요소를 병합할 때 merge함수가 $\mathrm{\Theta }(n)$‍번 실행된다면, mergeSort가 $\mathrm{\Theta }(n{\log }_{2}n)$‍번 실행된다는 것을 어떻게 보일 수 있을까요? 분할 정복 세 부분과 그것의 소요시간을 어떻게 계산해야하는지 생각해봅시다. 전체 배열에서 $n$‍개의 요소를 정렬한다고 가정합시다.

분할 단계와 결합 단계를 함께 생각해 봅시다. 분할 단계의 실행 시간인 $\mathrm{\Theta }(1)$‍은 결합 단계의 $\mathrm{\Theta }(n)$‍ 실행 시간과 비교하면 낮은 차수의 항입니다. 그러므로 분할 단계와 결합 단계를 합하여 $\mathrm{\Theta }(n)$‍ 시간이 걸린다고 생각할 수 있습니다. 확실하게 하기 위해 분할 단계와 결합 단계는 합하여 $cn$‍ 시간이 걸린다고 합시다. $c$‍는 어떤 상수를 나타냅니다.

문제를 간단히 하기 위해 만일 $n>1$‍일 경우 $n$‍은 항상 짝수라고 가정한다면 $n/2$‍을 고려할 때 이는 정수가 될 것입니다. ($n$‍이 홀수인 경우를 고려해도 big-Θ 표기법의 관점에서는 결과가 달라지지는 않습니다.) 그러므로 이제 $n$‍ 요소를 가진 하위 배열에서 mergeSort를 실행하는 시간은 $(n/2)$‍ 요소를 가진 하위 배열에서 mergeSort 를 실행하는 시간(정복 단계)의 두 배와 $cn$‍(분할 단계와 결합 단계—병합할 경우에 한함)을 합한 것이라 생각해 볼 수 있습니다.

이제 $n/2$‍ 요소에서 두 번의 재귀적 호출을 실행하는데 드는 시간에 대해 알아보아야 합니다. 이 두 재귀적 호출 각각에는 ($n/2$‍을 반으로 나누어야 하기 때문에)$(n/4)$‍ 개 요소의 하위 배열에 mergeSort를 실행하는 시간의 2배에 병합하는데 드는 $cn/2$‍을 더한 시간이 소요됩니다. $n/2$‍ 크기의 두 개의 하위 문제가 있고, 각각은 병합하는데 $cn/2$‍ 시간이 들기 때문에 $n/2$‍ 크기의 하위 문제를 병합하는데 드는 총 시간은 $2\cdot cn/2=cn$‍입니다

병합 시간을 "트리"로 그려봅시다.

컴퓨터공학자들은 트리를 실제 나무가 자라는 것과는 거꾸로 그립니다. 트리는 사이클(같은 장소에서 시작하고 끝나는 경로)이 없는 그래프입니다. 관습적으로 트리에서의 정점을 노드라고 부릅니다. 루트 노드는 가장 위에 놓입니다. 루트에는 $n$‍개 요소를 가진 $n$‍ 크기인 원래 배열의 하위 배열 크기가 표시됩니다. 아래 그림에서 루트는 두 자식 노드가 있는데 각각의 크기가 $n/2$‍인 두 하위 문제이므로 $n/2$‍로 표시합니다.

크기 $n/2$‍의 하위 문제에서는 크기 $(n/2)/2$‍ 또는 $n/4$‍의 두 하위 배열를 재귀적으로 정렬합니다. 크기 $n/2$‍의 하위 문제는 2개이므로 $n/4$‍ 크기의 하위 문제는 네 개가 있습니다. 네 가지 하위 문제 각각은 총 $n/4$‍개의 항목을 병합하기 때문에 네 개의 하위 문제 모두를 병합하는 시간은 $cn/4$‍이 됩니다. 4개 하위 문제의 총 시간을 합하면 $n/4$‍ 크기의 하위 문제 모두를 병합하는 시간이 $4\cdot cn/4=cn$‍라는 것을 알 수 있습니다.

$n/8$‍ 크기의 하위 문제에서는 어떻게 될까요? 각 문제가 여덟 개 있을 것이고 각각에 소요되는 병합 시간은 $cn/8$‍이므로 총 병합 시간은 $8\cdot cn/8=cn$‍이 될 것입니다.

하위 문제가 작아질수록 하위 문제의 수는 재귀과정의 각 단계마다 배가 되지만 병합 시간은 반으로 줄게 됩니다. 배가 되고 반으로 줄어들어 서로의 효과가 상쇄되기 때문에 각 재귀과정 단계에서 총 병합 시간은 $cn$‍이 됩니다. 결국은 하위 문제의 크기를 1로 줄이는 탈출 조건에 이르게 됩니다. 크기 1의 하위 배열을 정렬하려면 $p<r$‍ 인지 여부를 검사해야 하고 이 과정에 시간이 걸리기 때문에 $\mathrm{\Theta }(1)$‍가 소요됩니다. 크기 1의 하위 배열이 몇 개나 있을까요? 처음 시작할 때 $n$‍개 요소로 시작했으므로 하위 배열은 $n$‍개 있을 것입니다. 각각의 탈출 조건에는 $\mathrm{\Theta }(1)$‍ 시간이 소요되기 때문에 모두 합해 탈출 조건에 $cn$‍ 시간이 걸린다고 합시다.

이제 각 하위 문제 크기에서 병합 과정에 얼마나 걸릴지 알았습니다. mergeSort에 소요되는 총 시간은 모든 단계에서의 병합 시간을 합한 것입니다. 트리에 $l$‍ 레벨이 있다면 총 병합 시간은 $l\cdot cn$‍입니다. 여기서 $l$‍은 무엇일까요? 이제까지 $n$‍ 크기 문제의 하위 문제로 시작해서 하위 문제가 1로 줄어들 때까지 반복적으로 이를 반으로 줄였습니다. 이런 특성은 이진 검색을 분석할 때 본 적이 있었습니다. 그에 따르면 답은 $l={\log }_{2}n+1$‍이 됩니다. 예를 들어 $n=8$‍이라면 ${\log }_{2}n+1=4$‍이고 트리는 $n=8,4,2,1$‍의 4레벨로 이루어져 있습니다. 그러면 mergeSort에 드는 총 시간은 $cn({\log }_{2}n+1)$‍입니다. 이 실행 시간을 나타내기 위해 big-Θ 표기법을 사용한다면 낮은 차수 항($+1$‍) 과 상수 계수 ($c$‍) 를 버릴 수 있으므로 결국 실행 시간은 예상한 대로 $\mathrm{\Theta }(n{\log }_{2}n)$‍이 됩니다.

병합 정렬에 관한 또 한 가지 사실은 별 의미가 없습니다. 병합 과정 중 정렬될 전체 array의 반은 lowHalf에, 다른 반은 highHalf에 복사본을 만듭니다. 상수 개수의 요소보다 더 많이 복사하기 때문에 병합 정렬은 제자리에서 작동하지 않는다고 합니다. 그에 반해 선택 정렬과 삽입 정렬은 어떤 경우라도 배열 요소를 상수 개수 이상 복사하지 않기 때문에 모두 제자리에서 작동합니다. 저장 공간이 부족한 시스템이 존재하고 이 시스템에서는 제자리에서 작동하는 알고리즘을 선호하므로 컴퓨터 과학자들은 알고리즘이 제자리에서 작동하는지 여부에 대해서도 고려합니다.

위 자료는 다트머스 대학교 컴퓨터공학과의 토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.