CHAPTER 2 - 분할정복(Divide and Conquer)
- 문제의 입력를 두 개 이상의 작은 입력으로 나누고, 답을 얻기 위해 시도한다.
- 답을 얻지 못했다면, 또 각각의 입력 사례에 대해 분할을 한 뒤, 다시 시도한다.
- Divide and Conquer는 하향식(Top-Down) 방식의 접근법이다.
2.1 이분검색 (Binary Search)
- 이분 검색 알고리즘은 오름차순으로 정렬된 배열에서 실행가능하며, 수행 절차는 아래와 같다.
1. [Divide] 배열을 정 가운데 원소를 기준으로 반으로 분할한다. 찾고자 하는 수 x가 가운데 원소보다
작으면 왼쪽 배열을 선택한다. x가 가운데 원소보다 크면 오른쪽 배열을 선택한다.
2. [Conquer] 선택한 반쪽 배열을 정복한다. 즉, 선택한 반쪽 배열에 x가 있는지 재귀적으로 이분검색한다.
3. [Obtain] 선택한 반쪽 배열에서 얻은 답이 최종 답이다.
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);
}
}
- 이분 검색의 최악 시간 복잡도(Worst-Case Time Complexity)는,
$$ W\left(n\right)\ =\ W\left(\frac{n}{2}\right)\ +\ 1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ W\left(n\right)\ =\ \lg n\ +\ 1\ \ \in \ \Theta \left(\lg \ n\right) $$
2.2 Merge Sort
- 합병 정렬(Merge Sort)의 절차는 아래와 같다.
1. [Divide] 배열을 반으로 분할한다. (분할한 배열의 원소는 각각 n/2개 이다.)
2. [Conquer] 분할한 배열을 각각 따로 정렬한다.
3. [Obtain] 정렬한 두 배열을 합병하여 정렬한다.
void mergesort(int n, keytype S[])
{
if(n > 1) {
const int h = [n/2], m = n-h;
keytype U[1..h], V[1..m];
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);
}
}
void merge(int h, int m, const keytype U[], const keytype V[], keytype S[])
{
index i, j, k;
i = 1; j = 1; k = 1;
while( i <= h && j <= m) {
if(U[i] < V[j]) {
S[k] = U[i];
i++;
}
else {
S[k] = V[j];
j++;
}
k++;
}
if(i > h)
copy V[j] through V[m] to S[k] through S[h+m];
else
copy U[i] through U[h] to S[k] through S[h+m];
}
- Merge의 Worst-case Time Complexity W(h,m)은 아래와 같다.
(두 배열 U,V의 원소 개수는 h, m이다.)
$$ W\left(h,m\right)\ =\ h\ +\ m\ -\ 1 $$
- Mergesort의 Worst-case Time Complexity W(n)은 아래와 같다.
$$ W\left(n\right)\ =\ W\left(h\right)\ +\ W\left(m\right)\ +\ \left(h\ +m\ -1\right) $$
(1) W(h) : U를 정렬하는데 걸리는 시간
(2) W(m) : V를 정렬하는데 걸리는 시간
(3) (h+m-1) : 합병하는데 걸리는 시간
- 위의 식은 아래와 같이 표현될 수 있다.
$$ W\left(n\right)\ =\ 2W\left(\frac{n}{2}\right)\ +\ 1\ ,\ W\left(1\right)\ =\ 0 $$
$$ W\left(n\right)\ \ \in \ \Theta \left(n\ \lg \ n\right) $$
- MergeSort는 추가적으로 U와 V라는 배열을 만들어서 사용해야 하기 때문에, 추가적인 메모리가 필요하다.
(추가적으로 만들어지는 배열 원소의 총 개수는 대략 n(1+1/2+1/4+...) = 2n개 정도이다.)
- 이에 n개의 원소를 가진 배열 하나만을 사용하여 메모리 공간을 효율적으로 사용하는 MergeSort가 존재한다.
void mergesort2 (index low, index high)
{
index mid;
if(low < high){
mid = (low + high) / 2;
mergesort2(low, mid);
mergesort2(mid + 1, high);
merge2(low, mid, high);
}
}
void merge2(index low, index mid, index high)
{
index i, j, k;
keytype U[low .. high] // Merge에 필요한 local array
i = low; j = mid + 1; k = low;
while(i <= mid && j <= high) {
if(S[i] < S[j]) {
U[k] = S[i];
i++;
}
else {
U[k] = S[j];
j++;
}
k++;
}
if(i > mid)
move S[j] through S[high] to U[k] through U[high];
else
move S[i] through S[mid] to U[k] through U[high];
move U[low] through U[high] to S[low] through S[high];
}2.3 Quicksort(Partition Exchange Sort)
- Quicksort는 배열을 둘로 분할하고, 분할한 배열에 대해 각각 재귀 호출을 통해 정렬한다는 점이 Mergesort와 유사하다.
- 그러나, 빠른 정렬은 pivot을 설정하여 이 수보다 작은 원소는 왼쪽 배열로, 큰 원소는 오른쪽 배열로 가도록 하는 점에서 Mergesort와 다르다. 이에 pivot을 잘 설정하는 것이 중요하다.
void quicksort(index low, index high)
{
index pivotpoint;
if(high > low) {
partition(low, high, pivotpoint);
quicksort(low, pivotpoint - 1);
quicksort(pivotpoint + 1, high);
}
}
void partition(index low, index high, index& pivotpoint)
{
index i, j;
keytype pivotitem;
pivotitem = S[low]; // pivotitem으로 첫번째 원소를 선택함.
j = low;
for(i = low + 1; i <= high; i++){
if(S[i] < pivotitem){
j++;
exchange S[i] and S[j];
}
}
pivotpoint = j;
exchange S[low] and S[pivotpoint]; // pivotitem 값을 pivotpoint에 저장함.
}
- Partition은 첫째 원소를 제외한 모든 원소를 비교하므로, 시간복잡도는 아래와 같다.
$$ T\left(n\right)\ =\ n\ -1 $$
- 위의 Quicksort는 완전히 정렬된 배열을 정렬하는 경우가 Worst-case이다. (pivot이 항상 S[low])
$$ T\left(n\right)\ =\ T\left(0\right)\ +\ \ T\left(n-1\right)\ +\ n\ -1,\ n>0\ \ \ \ \ \ \ \ \ \ \ \ \ T\left(0\right)\ =\ 0 $$
T(0) : 왼쪽 배열을 정리하는데 걸리는 시간
T(n-1) : 오른쪽 배열을 정리하는데 걸리는 시간
n-1 : 분할(Partition) 하는데 걸리는 시간
$$ T\left(n\right)\ =\ \frac{n\left(n-1\right)}{2}\ \ \ \ \ \ \ \ \ \ \ W\left(n\right)\ =\ \frac{n\left(n-1\right)}{2}\in \Theta \left(n^2\right) $$
- 위의 Quicksort의 Average Time Complexity는,
$$ A\left(n\right)\ =\ \sum _{p=1}^n\frac{1}{n}\left[A\left(p-1\right)\ +\ A\left(n-p\right)\right]\ +\ n-1 $$
A(p-1) + A(n-p) : pivotpoint가 p일 때 부분 배열들을 정렬하는데 걸리는 평균시간
n-1 : 분할하는데 걸리는 시간
$$ A\left(n\right)\ \approx \left(n+1\right)2\ln n\ =\ \left(n+1\right)2\left(\ln 2\right)\left(\lg n\right) $$
$$ \approx \ 1.38\left(n+1\right)\lg n\ \in \ \Theta \left(n\lg n\right) $$
2.4 Strassen's Matrix Multiplication Algorithm
- 기본적인 행렬곱셈 알고리즘의 시간복잡도는,
$$ T\left(n\right)\ =\ n^3\ -\ n^2 $$
이므로, 실용적으로 사용하기 힘들다. 이에 Strassen은 곱셈을 기준으로 하든, 덧셈/뺄셈을 기준으로 하든지에
상관없이 시간복잡도가 3차보다 좋은 알고리즘을 발표하였다.
void strassen(int n, nxn_matrix A, nxn_matrix B, nxn_matrix& C)
{
if(n <= threshold)
compute C = A X B using the standard Algorithm.
else {
partition A into four matrices A11, A12, A21, A22;
partition B into four matrices B11, B12, B21, B22;
compute C = A X B using Strassen's method;
// example recursive call;
// strassen(n/2, A11 + A22, B11 + B22, M1);
}
}- Strassen에서의 곱셈의 수의 시간복잡도는 아래와 같다.
$$ T\left(n\right)\ =\ 7T\left(\frac{n}{2}\right)\ \ n>1\ 이며,\ n은\ 2의\ 거듭제곱 $$
$$ T\left(1\right)\ =\ 1 $$
$$ T\left(n\right)\ =\ n^{\lg 7}\approx n^{2.81}\in \Theta \left(n^{2.81}\right) $$
- Strassen에서의 덧셈/뺼셈의 수의 시간복잡도는 아래와 같다.
$$ T\left(n\right)\ =\ 7T\left(\frac{n}{2}\right)\ +\ 18\left(\frac{n}{2}\right)^2\ \ \ n>1\ 이며,\ n은\ 2의\ 거듭제곱 $$
$$ T\left(1\right)\ =\ 0 $$
$$ T\left(n\right)\ =\ 6n^{\lg 7}-6n^2\ \approx 6n^{2.81}\ -\ 6n^2\ \in \Theta \left(n^{2.81}\right) $$
2.5 분할정복법을 사용할 수 없는 경우
아래와 같은 두 경우에는 분할정복법을 피해야 한다.
1. 크기 n인 instance(사례)가 거의 n에 가까운 크기의 두 개 이상의 사례로 분할된다.
2. 크기 n인 instance(사례)가 n/c 크기의 거의 n개 사례로 분할된다.
첫번째 사례의 경우는 exponential-time(지수시간) 알고리즘이 나오고,
두번째 사례의 경우는 n^(theta(lgn))의 알고리즘이 나오게 된다.
-Reference-
Neapolitan, Richard E., 『Foundation of algorithms FIFTH EDITION』
'알고리즘 > 학부수업 이론' 카테고리의 다른 글
| Foundation of Algorithm - CHAPTER 3 (0) | 2022.05.08 |
|---|---|
| Foundation of Algorithm - CHAPTER 1 (0) | 2022.05.08 |