Divide-and-Conquer
-
분할(divide) : 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다.
-
정복 (Conquer); 나눈 작은 문제를 각각 해결
-
통합(Combine): (필요하다면) 해결된 해답을 모은다.
-
▶재귀적(recursive)방법으로 분할하고 정복하여 해결함 ▶이러한 문제 해결 방법을 top-down접근 방법
-
top-down접근 방법: 소프트웨어 개발에 기능 또는 구조위주(모듈단위)의 괁머으로 바라보면서 원하는 기능을 하향식으로 여러 개의 작은 부분으로 문제를 나누어 구체화하여 해결책을 찾는 방법
-
Divde & Conquer
procedure D&C(p,q)
int n, A(1:n);
int m, p,q; //1≤p≤q≤n
if SMALL(p,q) then return (G(p,q))
else { m =DIVIDE(p,q)
return COMBINE( D&C(p,m), D&C (m+1,q) ) }
End if -
이분검색 : 비내림차순으로 정렬된 배열S[1..n]
-
1) Recursive 알고리즘
index BYSRCH (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 BYSRCH (low, mid 1); } // 왼쪽 반을 선택
else { return BYSRCH (mid+1, high); } // 오른쪽 반 선택
} -
Analysis of Binary Search (recursive algorithm)
Let T(n) : 비교연산 한 횟수 number of comparisons by the algorithm in the worst case on lists with n elements.
T(n)= 1 (if n=1) , T(n)=T(n/2)+1 (if n>1) 중앙이랑 비교 + 배열의 크기 n/2로 줄음n= 2^k이라 하면
T(n) = T(n/2)+1
+T(n/2) = T(n/2^2 )+1
+T(n/2^2 ) = T(n/2^3 )+1
+. . .
- T(n/2^(k-1)= T(n/2^k)+1
T(n) = T(n/2^k)+1+1+ … +1(k개)
= T(n/n)+k = 1+k = 1+logn -> O( logn)
-
2) iterative 알고리즘 (재귀적X ) -O( logn)
BYSRCH2(int S[], index n) {
index low = 1, high = n, location= 0;
while (low <= high) { mid := (low + high) / 2
if (x == S[mid]) { location := mid; exit; }
else if (x < S[mid]) { high := mid –1; }
else { low := mid +1; } } -
평균적으로 O(n^2) 소요되는 알고리즘 : 선택정렬, 버블정렬, 삽입정렬
-
평균적으로 O() 소요되는 알고리즘 : 합병정렬（merge sort), 퀵정렬 (quick sort), 힙정렬(Heap)
-
합병정렬 (Mergesort) : 문제- n개의 정수를 비내림차순으로 정렬
-
Strategy : 1) split into two sets S[1..n/2], S[(n/2)+1 ..n] 2) each set is individually sorted and
-
3) resulting sequences are merged to produce a single sorted sequence of n elements
-
합병정렬 (Merge sort)은 입력이 2 개의 부분 문제로 분할하며 (divide), 부분문제의 크기가 1/2 로 감소하는 분할 정복 알고리즘이다. n 개의 숫자들을 n/2 개씩 2 개의 부분문제로 분할하고 , 각각의 부분문제를 재귀적으로 합병 정렬한 후 ,2개의 정렬된 부분을 합병 (merge) 하여 정렬한다 . 합병과정이 문제를 정복 (conquer) 하는 것이다.
-
merge알고리즘 : 두개의 정렬된 배열을 하나의 정렬된 배열로 합병
void merge int h, int m, const keytype U[], const keytype V[], const keytype S[]) {
index i = 1, j = 1, k = 1;
while (i <= h && j <= m) { //U배열 첫번째원소와 V배열 첫원소 비교시작해서 정렬,
if (U[i] < V[j]) {
S[k] = U[i]; i++; }
else {
S[k] = V[j];
j++; }
k++; }
if (i > h) //U배열의 원소가 다 끝나면, V배열 남은 뒷부분 그대로 복사
copy V[j] through V[m] to S[k] through S[h+m];
else //V배열의 원소가 다 끝나면, U배열 남은 뒷부분 그대로 복사
copy U[i] through U[h] to S[k] through S[h+m];
} -
Time Complexity of merge (worst case)
-
단위연산 : U[i]와 V[j] 의 비교연산
-
입력크기 : 2 개의 입력 배열에 각각 들어있는 항목의 개수, 즉 h 와 m
-
분석: 최악의 경우는 i = h , j =m -1 인 상태로 루프를 빠져 나갈 때이다 .
즉 V 의 처음m -1 개의 항목이 S 의 앞부분에 위치하고 , U 의 h 개의 모든 항목이 그 뒤에 위치하는 경우
단위연산의 실행 횟수는 h + m -1 이다 . 따라서, 합병하는 시간복잡도는 최악의 경우 w(h,m) =h + m -1, (약 2n) O(n) -
mergesort알고리즘 :
void mergesort int n, keytype S[])
const int h = n/2, m = n – h; //홀수일수도 있으니 m = n – h
keytype U[1..h], V[1..m];
if (n > 1) {
copy S[1] through S[h] to U[1] through U[h];
copy S[h+1] through S[n] to V[1] through V[m];
mergesort( h,U ); //재귀호출
mergesort( m,V );
merge (h,m,U,V,S ); } //합병호출
} -
Time Complexity of mergesort (worst case)
-
단위연산: merge에서 발생하는 비교연산
-
입력크기: 배열 S에 있는 항목의 개수 n
-
분석: 최악의 경우 T(n) = T(h) + T(m) + h + m - 1
여기서, T(h) 는 U를 정렬하는데 걸리는 시간이고, T(m)은 V를 정렬하는데 걸리는 시간, h+m-1은 합병하는데 걸리는 시간이ㅏ.
정수 n을 2k(k ≥1)이라고 가정하면 h=n/2, m=n/2이 된다.
따라서 Recurrence Equation: T(n) = 2T(n/2) + n-1 , n>1 이고 n= (k ≥1) , T(1) =0
T(n)= c for n=1 (c는 상수)
T(n)= 2 T(n/2) + an for n>1 (a 는 상수)
Let n=2^k이라고 하면
T(n) = 2· T(n/2) + a · n
+2·T(n/2) = 2 2 · T(n/2 2 ) + 2 · a · (n/2)
+2·T(n/2^2) = 2^3 · T(n/2^3 ) + 2^2 · a · (n/ 2^2)
+ …
+
+2^(k-1) · T(n/2^(k-1) = 2^k · T(n/2^k) + 2^(k-1) · a · (n/ 2^(k-1))
T(n) = 2^k · T(n/ 2^k) + a · n + a · n + … + a · n
= n· T(1) + a · n · k = c · n + a · n · k = c · n + a · n · logn
-> O(n logn)
- 공간복잡도 Space Complexity of mergesort (worst case)
- 제자리정렬(in-place sort) 알고리즘 : 입력을 저장하는데 필요한만큼 저장장소를 사용하지 않고 정렬함.
- Mergesort알고리즘은 입력인 배열 S이외에 U와 V를 추가로 만들어서 사용하므로 제자리정렬이 아님
- Mergesort를 재귀호출할 때마다 크기가 S의 반이 되는 U와 V가 추가적으로 필요하다. (merge 알고리즘에서는 추가적인 저장장소를 만들지 않음).
mergesort를 재귀호출할 때마다 처음 S의 크기가 n이면, 추가적으로 필요한 U와 V의 저장장소 크기의 합은 n이다.
추가적으로 필요한 총 저장장소의 크기: n + n/2 + n/4 + … = 2n
-> 공간복잡도는 2n ⋲ O(n)
