분할 정복식 알고리즘

여태까지 살펴본 정렬 알고리즘 두 개, 선택 정렬과 삽입 정렬의 최대 실행시간은 $\mathrm{\Theta }(n^2)$‍으로 나타낼 수 있습니다. 입력하는 배열의 크기가 크다면 이 알고리즘으로 정렬하는데 매우 오랜 시간이 걸릴수 있습니다. 이번 수업과 다음 수업에서는 속도가 더 빠른 정렬 알고리즘 두 개(병합 정렬: Merge sort, 빠른 정렬: Quick sort)를 더 배우게 될 것입니다. 특히 병합 정렬의 실행시간은 모든 경우에 대해 $\mathrm{\Theta }(n\lg n)$‍으로, 빠른 정렬의 최대 시간은 $\mathrm{\Theta }(n^2)$‍이지만 가장 빠르면 $\mathrm{\Theta }(n\lg n)$‍으로 나타납니다. 아래 표에 정렬 알고리즘 네 개와 실행시간을 보면서 이해해봅시다.

병합 정렬과 빠른 정렬 두 가지 정렬 방법은 모두 재귀 알고리즘 설계 패러다임을 기반으로 삼고 있습니다. 분할 정복으로 통칭하는 이 패러다임은 한 문제를 유형이 비슷한 여러 개의 하위 문제로 나누어 재귀적으로 해결하고 이를 합쳐 원래 문제를 해결합니다. 분할 정복 방식이 하위 문제를 재귀적으로 해결하기 때문에 하위 문제 각각은 원래 문제보다 범위가 작아야 하며 하위 문제는 각 문제마다 탈출 조건이 존재해야 합니다. 분할 정복 알고리즘을 이해하기 위해 다음과 같이 세 부분으로 나눠서 생각해봅시다.

분할 정복 알고리즘의 단계를 분할, 정복, 합치기 세 개로 나누면 쉽게 기억할 수 있습니다. 분할 단계에서 하위 문제가 두 개 생긴다고 가정하면 이 알고리즘은 아래 그림으로 정리할 수 있습니다 (일부 분할 정복 알고리즘은 하위 문제 두 개 이상으로 이루어질 수 있습니다).

재귀적 문제를 두 개 더 만들어 확장할 경우 다음과 같이 나타낼 수 있습니다.

분할 정복 알고리즘은 최소한 두 개의 하위 문제를 생성하므로 여러번 재귀 호출을 합니다.

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