[알고리즘] 분할정복법

단계별 접근

1. 문제를 나누기

2. 풀 수 있으면 풀고 그렇지 않으면 더 작게 나누기

3. 만약 필요한 경우 문제들의 답을 결합.

 

이진검색법의 예시

1. divide :
배열을 반으로 나누기. 찾으려는 값과 중앙 값 비교. 비교 결과에 따라 배열 선택

2. conquer :

찾으려는 값의 위치를 찾아냄

public static index location(index low, index high){
	index mid;
    if(low>high) return 0;
    else {
    	mid= (low+high)/2;
        if(x==S[mid])
        	return mid;
     	else if(x<S[mid])
        	return location(low, mid-1)
        else
        	return location(mid+1, high)
    }
}

최악의 경우 시간복잡도 구하기

Basic Operation (복잡도에 가장 큰 영향을 미치는 연산) : x와 S[mid]의 비교

Input Size : n, 배열의 요소 갯수

(n을 2^k라고 가정)

n이 1보다 클 때, W(n)=W(n/2)+1=(W(n/2^2)+1)+1....(계속 치환)=1+k=1+lgn

합병 정렬의 예시

1. divide :

배열을 반으로 나눠 두개로 만듬

2. conquer :

배열이 충분히 작으면 적절히 정렬, 그렇지 않으면 다시 나눔

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],
        		V= new keytype[1....m];
        copy S[1:h] to U[1:h];
        copy s[h+1:n] to V[1:m];
        mergeSort(h,U);
        mergeSort(m,V);
        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[i]){
        	S[k]=U[i]; i++;}
        else{
            S[k]=V[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];
}

최고의 경우 시간 복잡도

Basic Operation : U[i]와 V[i]의 비교연산

Input Size : h, m, 각 배열의 원소 갯수

두 배열이 모두 정렬된 상태로 서로 비교하지 않아도 되는 경우가 가장 적은 연산을 할 것.

큰 길이의 배열 첫 원소가 짧은 길이의 원소와 비교하는 행위만 하여 연결만 하면 되므로

B(h,m)=min(h,m)

 

최악의 경우 시간 복잡도.

모든 원소를 비교해야 되는 경우

W(h,m) = h+m-1