알고리즘 디자인 기법 (Divide and Conquer)

O 분할 정복 기법

- 분할 정복

순서	설명
Step 1. Divide	문제를 작은 문제로 쪼갠다.
Step 2. Conquer	문제가 풀 수 있을 만큼 작아지면 문제를 직접 풀고, 그렇지 않으면 문제를 재귀로 푼다.

- 구현

function F(x):   if F(x)의 문제가 간단 then:     return F(x)을 직접 계산한 값   else:     x를 y1, y2로 변환     F(y1)과 F(y2)를 호출     return F(y1), F(y2)로부터 F(x)를 구한 값

- Merge Sort (예제1)

• 과정

순서	설명
Step 1. Divide	배열을 절반으로 나눠 서브배열 2개를 만든다.
Step 2. Conquer	서브배열이 충분히 작으면, 정렬하고 그렇지 않으면 재귀로 정렬한다.
Step 3. Combine	정렬된 서브배열을 하나의 정렬된 배열로 만든다.

• 그림

• 구현

public static void mergeSort(int n, keytype[] S){   if(n>1){     const int h = floor(n/2), m=n-h;     keytype[] U = new keytype[1..h],     keytype[] V = new keytype[1..m];     // Divide     copy S[1:h] to U[1:h];     copy S[h+1:n] to V[1:m];     // Conquer     mergeSort(h, V);     mergeSort(m, V);     // Combine     merge(h, m, U, V, S);   } }

public static void merge(int h, int m, keytype[] U, keytype[] V, keytype[] S){     index I=1, j=1, k=1;     while(I<=h && j<=m){         if(U[I] < V[j]){             S[k] = U[I]; I++;         }else{             S[k] = U[j]; j++;         }         k++;     }     if(I > h)         copy V[j:m] to S[k:h+m];     else         copy U[I:h] to S[k:h+m]; }

• 시간복잡도

mergeSort 함수 안에 merge 함수가 있기에 merge 함수부터 시간복잡도를 계산하자. merge 함수 Worst Case를 보면, 두 서브배열이 최대한 비교 연산을 많이 할 때 발생

<그림> merge 함수 Worst Case

merge 함수의 시간복잡도(Worst Case)는 h+m-1 이다.   mergeSort 함수의 시간복잡도:   n=2^k로 가정하고, h=m=n/2로 가정했을 때, W(n) = W(n/2) + W(n/2) + n/2 + n/2 – 1      = 2W(n/2) + n – 1   그러므로 W(n) = (nlg n) - (n-1)-1 이고 O(nlg n)을 가진다.

- Quick Sort(예제 2)

• 과정

순서	설명
Step 1. Divide	리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다.
Step 2. Conquer	분할된 서브 배열을 재귀로 정렬한다.

• 구현

public static void quickSort(index low, index high){   index pivotPoint;   if(high > low){     // Divide     pivotPoint = partition(low, high);     // Conquer     quickSort(low, pivotPoint-1);     quickSort(pivotPoint+1, high);   } }

public static index partition(index low, index high){   index I, j, pivotPoint; keytype pivotItem;   pivotItem = S[low]  ;   j = low;   for(I=low +1; I<=high; I++){     if(S[I]<pivotItem){       exchange S[I] and S[++j];     }   }   pivotPoint = j;   exchange S[low] and S[pivotPoint];   return pivotPoint; }

• 시간복잡도

quickSort 함수 안에 partition 함수가 있기에 partition 함수부터 시간복잡도를 계산하자.

partition 함수는 Every Case로 어떤 상황에서도 시간복잡도 T(m)은 m-1로 동일하다.   quickSort 함수는 Worst Case와 Average Case로 나뉘는데, Worst Case는 이미 배열이 정렬되어 있을 때 발생한다.     이미 정렬된 배열에서는 partition 함수에서 피벗에 변경이 없고 계속 쓸데없는 비교만 한다. 즉, 큰 배열을 정중으로 분할하지 못하고 원소 하나씩 분할하고 있는 상황이다. 이럴 경우 quickSort는 O(n^2) 시간 복잡도를 가진다.   Average Case는 다음과 같이 풀 수 있다.   quickSort의 Average Case 시간 복잡도는 O(nlg n)을 가진다.

- Merge Sort vs Quick Sort

Algorithm	Data Structure	Time Complexity:Best	Time Complexity:Average	Time Complexity:Worst
Quick Sort	Array	O(n log(n))	O(n log(n))	O(n^2)
Merge sort	Array	O(n log(n))	O(n log(n))	O(n log(n))

※ Quick Sort의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다.