[Algorithm Part 3] 3. Divide-and-Conquer algorithms

이번 글에서는, divide-and-conquer 기법을 활용한 유명 알고리즘에 대해 살펴볼 것이다.

---

1. Quicksort

Problem

정렬 문제다. 즉, 크기가 n인 배열(=S)을 정렬하는 문제다.

Algorithm

1. pivot item(=S[0])으로 배열 S를 partition(=분할)한다.
   1. pivot item보다 작으면 pivot 왼쪽으로 이동
   2. pivot item보다 크면 pivot 오른쪽으로 이동
2. 분할된 2개 부분 배열을 각각 정렬한다. (만약, 부분 배열을 더 분할할 수 있다면, 재귀를 통해 정렬한다.)
3. 정렬된 부분 배열 2개와 pivot item을 연결시켜, original 배열을 정렬한다.

Analysis

base operation: pivot item과 S[i]간의 비교 연산

input size: n(=size of array)

worst-case time complexity (already sorted):

$$\begin{matrix} W(n) &=& W(0) + W(n - 1) + n - 1 \\ &=& \frac{n(n-1)}{2} \\ &\in& \Theta(n^2)\end{matrix}$$

average-case time complexity (randomly shuffled):

$$\begin{matrix} A(n) &=& \sum_{p=1}^{n} \frac{1}{n} [A(p-1) + A(n-p)] + n - 1 \\ &=& \frac{2}{n} \sum_{p=1}^n A(p-1) + n - 1 \\ &=& 1.38(n+1) \lg n \\ &\in& \Theta(n\lg n)\end{matrix}$$

---

2. Stressen's Matrix Multiplication Algorithm

Problem

행렬 곱 연산

Algorithm

1. 행렬 $A$, $B$를 각각 4개의 부분 행렬($A_{11}, A_{12}, A_{21}, A_{22}$ and $B_{11}, B_{12}, B_{21}, B_{22}$)로 나눈다.
2. 분할된 부분 행렬의 합을 가지고 행렬 곱 연산을 진행한다. (만약, 부분 행렬의 합을 더 나눌 수 있다면, 재귀를 통해 행렬 곱 연산을 한다.)
   1. $M_1 = (A_{11} + A_{22})(B_{11} + B_{22})$
   2. $M_2 = (A_{21} + A_{22})B_{11}$
   3. $M_3 = A_{11}(B_{12} - B_{22})$
   4. $M_4 = A_{22}(B_{21} - B_{11})$
   5. $M_5 = (A_{11} + A_{12})B_{22}$
   6. $M_6 = (A_{21} - A_{11})(B_{11} + B_{12})$
   7. $M_7 = (A_{12} - A_{22})(B_{21} + B_{22})$
3. 7개 행렬($M_1 \sim M_7$)을 기반으로 , $A$, $B$의 행렬 곱 연산을 진행한다.

$$\begin{bmatrix} M_1 + M_4 - M_5 + M_7 & M_3 + M_5 \\ M_2 + M_4 & M_1 + M_3 - M_2 + M_6 \end{bmatrix}$$

Analysis 1

base operation: 행렬 곱

input size: n (=$A$,$B$의 행, 열의 개수)

every-case time complexity:

$$\begin{matrix} T(n) &=& 7T\left(\frac{n}{2}\right) \\ &=& n^{\lg 7} \approx n^{2.81} \\ &\in& \Theta(n^{2.81})\end{matrix}$$

Analysis 2

base operation: 행렬 합 및 차

input size: n (=$A$, $B$의 행, 열의 개수)

every-case time complexity:

$$\begin{matrix} T(n) &=& 7T\left(\frac{n}{2}\right) + 18\left(\frac{n}{2}\right)^2 \\ &=& 6n^{\lg 7} - 6n^2 \approx 6n^{2.81} - 6n^2 \\ &\in& \Theta(n^{2.81})\end{matrix}$$

 

행렬 곱은 적어도 $\Theta(n^2)$의 시간 복잡도를 갖고 있으며, 이를 만족하는 알고리즘은 아직 발견되지 않았다.

---

3. Multiplication of Large Integers

Problem

n자리수 정수 $u$, $v$의 곱 연산

Algorithm

1. n자리수 정수를 2개 n/2자리수 정수로 표현(or 분할)한다.
   ($u = x \times 10^{n/2} + y, \quad v = w \times 10^{n/2} + z$)
2. n/2자리수 정수의 곱 연산을 진행한다. (만약, n/2자리수 정수를 더 분할할 수 있다면, 재귀를 통해 곱 연산을 한다.)
   
   1. $x \times w$
   2. $(x + y) \times (w + z)$
   3. $yz$
3. n/2자리수 정수의 곱 연산을 기반으로, $u$와 $v$의 곱 연산을 진행한다.

$$uv = xw \times 10^{n} + [(x+y)(w+z) - (xw + yz)] \times 10^{n/2} + yz$$

Analysis

base operation: 한자리 숫자 조작(=manipulation)

input size: n(= $u$, $v$의 자리수)

worst-case time complexity:

$$\begin{matrix} W(n) &=& 3W\left(\frac{n}{2}\right) + cn \\ &=& cn^{\lg3} \approx n^{1.58} \\ &\in& \Theta(n^{1.58})\end{matrix}$$

---

4. RSelect (=randomize)

Problem

kth order statistic problem 즉, 크기가 n인 배열(=S)에서 k번째로 작은 item을 찾는 문제다.

이는 정렬 문제보다 쉬운 문제다.

Algorithm

1. pivot item(=S[0])으로 배열 S를 partition(=분할)한다.
   1. pivot item보다 작으면 pivot 왼쪽으로 이동
   2. pivot item보다 크면 pivot 오른쪽으로 이동
2. 만약 pivot index(=j)가 k일 경우, pivot item 반환. 그렇지 않으면,
   1. k가 pivot index보다 작다면, 왼쪽 부분 배열에서 $k$번째로 작은 item을 찾는다.
   2. k가 pivot index보다 크다면, 오른쪽 부분 배열에서 $k - j$번째로 작은 item을 찾는다.
   3. 만약, 부분 배열을 더 분할할 수 있다면, 재귀를 통해 item을 찾는다.
3. 부분 배열에서 찾은 item이 solution이다.

Analysis

base operation: pivot item과 S[i]간의 비교 연산

input size: n(=size of array)

worst-case time complexity (already sorted):

$$\begin{matrix} W(n) &=& W(n - 1) + n - 1 \\ &=& \frac{n(n-1)}{2} \\ &\in& \Theta(n^2)\end{matrix}$$

average-case time complexity (randomly shuffled):

$$\begin{matrix} A(n) &=& \frac{1}{n} \sum_{p=1}^n A(p-1) + n - 1 \\ &=& (n-1)(1 + 1/2 + 1/4 + \cdots) \approx 2n \\ &\in& \Theta(n)\end{matrix}$$

---

5. DSelect (=deterimistic)

Problem

kth order statistic problem 즉, 크기가 n인 배열(=S)에서 k번째로 작은 item을 찾는 문제다.

Algorithm

1. pivot(=MoM)을 구한다.
   1. 크기가 5인 부분 배열의 중앙값을 모두 구해, 중앙값 집합($m = (m_1, m_2, \cdots, m_{n/5})$)을 만든다.
   2. $m$의 중앙값(=Median-of-Median)을 구한다. 즉, $m$에서 $m/5$번째로 작은 item을 찾는다. (만약, $m$을 더 나눌 수 있다면, 재귀를 통해 MoM을 구한다.)
2. 만약 MoM index(=j)가 k일 경우, MoM item 반환. 그렇지 않으면,
   1. k가 pivot index보다 작다면, 왼쪽 부분 배열에서 $k$번째로 작은 item을 찾는다.
   2. k가 pivot index보다 크다면, 오른쪽 부분 배열에서 $k - j$번째로 작은 item을 찾는다.
   3. 만약, 부분 배열을 더 분할할 수 있다면, 재귀를 통해 item을 찾는다.
   4. 이때, $\frac{3n}{10} < j < \frac{7n}{10}$을 만족한다.
3. 부분 배열에서 찾은 item이 solution이다

Analysis

base operation: pivot item과 S[i]간의 비교 연산

input size: n(=size of array)

worst-case time complexity (already sorted):

$$\begin{matrix} W(n) &=& n + W(n/5) + n - 1 + W\left(\frac{7n}{10}\right) \\ &\in& \Theta(n)\end{matrix}$$