divide-and-conquer 분할 정복 (feat. merge sort)

 

• 분할정복의 3단계
  1. Divide : 문제를 동일한 문제의 작은 인스턴스인 여러 하위 문제로 나눔.
  2. Conquer : 하위 문제들을 재귀적으로 풀어서 정복. (하위 문제의 크기가 충분히 작다면, 간단한 방법으로 하위 문제를 해결)
  3. Combine : 하위 문제에 대한 해결책을 원래 문제에 대한 해결책으로 결합.

 

Merge Sort 

Merge Sort 정렬법

Merge Sort의 문제 해결법은 원본 배열(A)을 복사 한뒤 절반으로 나눈다 (L, R) 

절반으로 나눈 두 배열(L,R)이 정렬이 되어있다는 가정하에 두 배열의 값을 비교하면서 A배열을 정렬한다.

이 정렬 매커니즘을 L,R에도 재귀로 적용 시킨다면 그것이 merge sort

 

정렬된 노드를 하위에서 부터 merge

L,R 배열의 크기가 가장 작아질때까지 분할하기로 하고(Divide) 

재귀를 이용하여 가장 하위노드 L,R 을 이용하여 비교 정렬(Conquer)한 뒤

그 결과물 A를 또다른 L,R 노드로 활용하면서 문제를 해결 (Combine) 한다. 

 

 

+) merge sort의 시간복잡도

T(n) = cn log n + cn

c는 상수이므로 생략 하면 merge sort의 시간복잡도는 O(nlogn) 이 된다.