Foundation of Algorithm - CHAPTER 2

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);
  }
}

The steps when searching with Binary Search

 

- 이분 검색의 최악 시간 복잡도(Worst-Case Time Complexity)는,

$$W\left(n\right)=W\left(\frac{n}{2}\right)+1W\left(n\right)=\lg n+1\in \mathrm{\Theta }(\lg n)$$

---

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];
}

​

The steps when searching with Merge Sort

 

- Merge의 Worst-case Time Complexity W(h,m)은 아래와 같다.
  (두 배열 U,V의 원소 개수는 h, m이다.)

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

- Mergesort의 Worst-case Time Complexity W(n)은 아래와 같다.

$$W\left(n\right)=W\left(h\right)+W\left(m\right)+(h+m-1)$$

(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 \mathrm{\Theta }(n\lg n)$$

- 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에 저장함.
}

The steps when searching with Quick Sort

Paritition Algorithm

 

- Partition은 첫째 원소를 제외한 모든 원소를 비교하므로, 시간복잡도는 아래와 같다.

$$T\left(n\right)=n-1$$

- 위의 Quicksort는 완전히 정렬된 배열을 정렬하는 경우가 Worst-case이다. (pivot이 항상 S[low])

$$T\left(n\right)=T\left(0\right)+T(n-1)+n-1,n>0T\left(0\right)=0$$

T(0) : 왼쪽 배열을 정리하는데 걸리는 시간
T(n-1) : 오른쪽 배열을 정리하는데 걸리는 시간
n-1 : 분할(Partition) 하는데 걸리는 시간

$$T\left(n\right)=\frac{n(n-1)}{2}W\left(n\right)=\frac{n(n-1)}{2}\in \mathrm{\Theta }\left(n^2\right)$$

- 위의 Quicksort의 Average Time Complexity는,

$$A\left(n\right)=\sum _{p=1}^n\frac{1}{n}[A(p-1)+A(n-p)]+n-1$$

 

A(p-1) + A(n-p) : pivotpoint가 p일 때 부분 배열들을 정렬하는데 걸리는 평균시간
n-1 : 분할하는데 걸리는 시간

$$A\left(n\right)\approx (n+1)2\ln n=(n+1)2(\ln 2)(\lg n)$$

$$\approx 1.38(n+1)\lg n\in \mathrm{\Theta }(n\lg n)$$

---

2.4 Strassen's Matrix Multiplication Algorithm

- 기본적인 행렬곱셈 알고리즘의 시간복잡도는,

$$T\left(n\right)=n^3-n^2$$

이므로, 실용적으로 사용하기 힘들다. 이에 Strassen은 곱셈을 기준으로 하든, 덧셈/뺄셈을 기준으로 하든지에
상관없이 시간복잡도가 3차보다 좋은 알고리즘을 발표하였다.

The partitioning into submatrics in Strassen's Algorithm

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 \mathrm{\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 \mathrm{\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』