5알고리즘 분석

 

병합 정렬은 주어진 문제를 절반으로 나눈 다음 각각을 재귀 호출로 풀어 가는 방식입니다. 이처럼 큰 문제를 작은 문제로 나눠서(분할하여) 푸는(정복하는) 방법을 알고리즘 설계 기법에서는 ‘분할 정복(divide and conquer)’이라고 부릅니다. 입력 크기가 커서 풀기 어려웠던 문제도 반복해서 잘게 나누다 보면 굉장히 쉬운 문제(종료 조건)가 되는 원리를 이용한 것입니다. 분할 정복은 잘 활용하면 계산 복잡도가 더 낮은 효율적인 알고리즘을 만드는 데 도움이 됩니다.

분할 정복을 이용한 병합 정렬의 계산 복잡도는 O(n·logn)으로 선택 정렬이나 삽입 정렬의 계산 복잡도 O(n²)보다 낮습니다. 따라서 정렬해야 할 자료의 개수가 많을수록 병합 정렬이 선택 정렬이나 삽입 정렬보다 훨씬 더 빠른 정렬 성능을 발휘합니다.

예를 들어 대한민국 국민 오천만 명을 생년월일 순서로 정렬한다고 생각해 봅시다. 입력 크기가 n = 50,000,000일 때 n²은 2,500조이고 n·log n은 약 13억입니다. 워낙 큰 숫자라 감이 잘 오지 않는다고요? 2,500조는 13억보다 무려 200만 배 정도 큰 숫자입니다. 이 사실을 알면 O(n²) 정렬 알고리즘과 O(n·logn) 정렬 알고리즘의 계산 시간이 얼마나 많이 차이 나는지 짐작할 수 있을 것입니다.