[알고리듬] 5주차: Divide-and-Conquer

Master Theorem

ⓐ $f(n) = \Omega(n^{\log_c{r} + \epsilon}$ = $f(n)$의 지수가 $\log_c{r}$에 비해 크면

$T(n) = O(f(n))$

   

ⓑ $f(n) = \Theta(n^{\log_c{r}}\log^k{n}) \;\;for\;\;some\;\; k \geq 0$ = $f(n)$의 지수가  $\log_c{r}$과 비슷하면

$T(n)=O(f(n)\cdot\log{n})$

 

ⓒ $f(n) = O(n^{\log_c{r} - \epsilon})$= $f(n)$이  $n^{\log_c{r}}$에 비해 작으면

$T(n) = O(n^{\log_c{r}})$

 

$f(n)$은 non-recursive한 부분

 

Solving Recurrence

$T(n)=2T(n/2) + O(n)$

$r = 2, c = 2, \log_c{r} = 1, f(n)= n$

-> $\log_c{r}$ = $n$의 지수 -> $T(n) = O(f(n)\;\log{n}) = O(n\log{n})$

 

 

Recursion tree

각 노드에 대해 주어진 입력의 사이즈를 노드 옆에 써본다

이를 $f(n)$에 적용한다

level 별로 다 더한다

 

$T(n)=T(2n/3) + T(n/3) + O(n)$

 

각 level의 합은 $n$

tree의 높이는 이진트리긴 한데 왼쪽 방향은 더 빨리 base case에 도달하고 오른쪽은 늦게 도달한다.

-> 오른쪽으로 치우친 형태의 이진 트리가 된다.

 

오른쪽으로 갈 때는 $\frac{2}{3}$의 거듭제곱 꼴로 줄어든다. leaf node가 되려면 결국 값이 1이 되어야 하므로

$(\frac{2}{3})^{h}n = 1$을 풀면 됨 (Hint: 양변에 로그를 취한다)

 

 

 

 

Multiplication

$n$자리 정수 $x$와 $y$

 

$O(n^2)$: Long multiplication, Lattice multiplication, Peasant multiplication

 

Divide-and-Conquer

어떻게 분할할까?

분할된 subproblem을 풀고 어떻게 마무리할까?

 

 

Ex) $n=4$, $x=3627$, $y=9021$

36 | 27, 90 | 21로 나눠보자

3627 × 9021

= (36×100 + 27) + (90×100 + 21)

= (36×90)×10000 + (36×21 + 27×90)×100 + 27×21

 

일반화하면

x와 y를 반으로 잘라서 $m = \lceil n/2 \rceil$에 대해 $x = 10^ma + b$, $y = 10^mc + d$

ac, bc, ad, bd를 Recursion으로 계산하고

$10^{2m}ac + 10^m(bc+ad) + bd$를 계산

 

반환값은 사실상 끝에 0만 붙이는 것(10진수에 대한 shift 연산)

 

Correctness

$xy=10^{2m}ac+10^m(bc+ad)+bd$

 

Time complexity

Recursion part: $\frac{n}{2}$ 크기의 instance에 대해 4번의 recursive call

Non-recursion part: $O(n)$ (덧셈 + shift)

$T(n)$을 시간복잡도 함수라 하면

$T(n) = 4T(n/2) + O(n)$ -> $O(n^2)$

$c = 2,\;r = 4,\; \log_c{r}=2$

$n^{\log_c{r}} > f(n)=n$이므로 $O(n^2)$가 됨

 

 

 

Fast multiplication

$O(n^2)$보다 더 빠르게는 안 될까?

: 문제에 대한 질문 -> Complexity theory

 

$xy=(10^ma + b)(10^c+d) = 10^{2m}ac+10^m(bc+ad)+bd$

사이즈를 반으로 나누긴 했지만 결국 재귀호출을 4번 해야 함 ($ac$, $bc$, $ad$, $bd$)

 

$bc+ ad$를 보자

$bc + ad - ac - bd$를 하면

$(a-b)(d-c)$

 

$\therefore\;\;\;\;bc + ad$

$= (a-b)(d-c) + ac + bd$

$= ac + bd - (b-a)(d-c)$

-> $ac$, $bd$, $bc + ad$를 알면 $xy$를 계산할 수 있다.

 

 

① $ac$, $bd$ 를 계산한다.

② $bc+ad$를 구하기 위해 아까 계산한 $ac$, $bd$를 구한 후 $(a-b)(c-d)$를 뺀다.

-> 곱셈 횟수가 4번에서 3번으로 줄었다.

 

결론적으로 $ac$, $bd$, $(a-b)(c-d)$만 recursive call로 구하면 됨

 

Correctness

$xy=10^{2m}ac+10^m(bc+ad)+bd$

$bc + ad = ac + bd - (b-a)(d-c)$

 

Time complexity

Recursion part: $\frac{n}{2}$사이즈의 instance 3번 recursive call

Non-recursion part: $O(n)$

따라서 시간복잡도 함수를 $T(n)$이라 하면

$T(n)$

$= 3T(n/2) + O(n)$

$=O(n^{\log_2{3}}) = O(n^{1.58496})$

 

 

 

Matrix multiplication

Input: $n \times n$ 행렬 $A$와 $B$

Output: $C = AB$

 

$O(n^3)$: 그냥 3중 for 문

 

Divide-and-Conquer

$m \times m$ 모양이 되도록 나눠야 하니까 가로세로 반씩 나누자

$e.g.\;\;\;\;A=\begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A{22}\end{bmatrix}$ -> $\frac{n}{2} \times \frac{n}{2}$ 행렬

 

$\begin{bmatrix} C_{11} & C_{12} \\ C_{21} & C_{22}\end{bmatrix}$

$= \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22}\end{bmatrix}\begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22}\end{bmatrix}$

$= \begin{bmatrix} A_{11}+B_{11} & A_{12} + B_{12} \\ A_{21} + B_{21} & A_{22} + B_{22}\end{bmatrix}$

 

A와 B를 4개의 부분행렬로 나누고 $\frac{n}{2} \times \frac{n}{2}$ 행렬의 곱셈을 8번 하면 됨

$A_{11}B_{11}, A_{12}B_{21}, A_{11}B_{12}, A_{12}B_{22}, A_{21}B_{11}, A_{22}B_{21}, A_{21}B_{12}, A_{22}B_{22}$

그리고 행렬 덧셈과 끼워넣기로 마무리

$n \;\times\; n$ 행렬 두 개의 곱을 Divide-and-conquer로 계산할 때 걸리는 시간

$T(n) = 8T(n/2) + O(n^2) = O(n^3)$

절반으로 나눴지만 곱셈을 8번이나 해서 효율 상의 이득이 없음

 

현재 최선은 O(n^{2.3728639})

아직 정확한 최선은 안 나옴

 

 

 

Binary Search

정렬된 배열에서의 탐색

정렬된 배열과 $k$가 주어지고, $k$의 위치를 구한다. (없으면 보통 $-1$ 리턴)

 

① 중간값과 비교

② $k$가 작으면 왼쪽에서 탐색, $k$가 크면 오른쪽에서 탐색

탐색하고 반으로 나눠서 탐색하고, ... -> 분할해서 같은 문제의 instance를 해결: 알고보면 Divide-and-Conquer

int binary_search (int A[], int k, int a, int b)
    if (a > b) return -1;
 
    int mid = (a + b) / 2;
 
    if (A[mid] > k) return binary_search(A, k, a, mid - 1);
    else if (A[mid] < k) return binary_search(A, k, mid + 1,
    else return mid; 
}

점화식: $T(n) = T(n/2) + O(1)$ (사실 $k$는 빼고 탐색하니까 $n/2$보다 살짝 작음)

$c = 2,\; r = 1,\; \log_c{r} = 0,\; f(n) = n^0$

 

 

 

 

Selection

$A[1..n]$에서 $k$번째로 작은 정수 (ranking이 $k$인 정수)

 

O(n\log{n}): 그냥 정렬해서 뽑아냄(Reduction)

 

 

Divide-and-Conquer: Quickselect(One-armed quicksort)

($1 \leq k < n$ 가정)

 

pivot을 고른 후 $Partition$한다(아무거나 고름)

$r$은 pivot의 랭킹(pivot이 몇 번째로 작은 값인지)

$k-r$: $r$번째까지는 버리고 그 다음부터 찾는 거니까 $k-r$로 탐색해야 함

 

 

Correctness

Trivial.

 

Time complexity

Quicksort와 비슷

$T(n) leq max\{T(r-1), T(n-r)\} + O(n)$

최악의 경우에 대한 시간 복잡도를 계산하므로 $max\{T(r-1), T(n-r)\}$

 

$T(n) \leq max_{1 \leq r \leq n}\;\ \max\{T(r-1), T(n-r)\} + O(n)$

$r = 1$ 또는 $r = n$일 때 최댓값

 

$T(n) \leq T(n-1) + O(n)$

$n$이 하나씩 줄면서 그 때마다 $O(n)$이니까 $O(n^2)$임을 알 수 있음

 

What is good pivot?

Quicksort처럼 pivot에 따라 성능이 달라짐

정가운데가 아니더라도 중간에 있는 위치 -> $0 < a < 1$에 대해 $r=an$인 pivot

이 경우 점화식 $T(n) leq max\{T(r-1), T(n-r)\} + O(n)$은

$T(n) leq T(max(a, 1-a)\;\times\;n) + O(n)$

-> $T(n) = O(n)$

 

Ex) $a=\frac{1}{3}$

$max(\frac{1}{3}, \frac{2}{3}) = \frac{2}{3}$

$\because\;\; T(n)$

$\leq T(\frac{2}{3} n) + O(n)$

$= n+ \frac{2}{3}n + \frac{4}{9}n + \cdots$

$= (1 + \frac{2}{3} + \frac{4}{9} + \cdots)n$

$= cn$

$= O(n)$

 

즉 중간값과 비슷한 pivot을 찾을 수 있다면 selection을 $O(n)$에 할 수 있다.

 

 

Good pivot: Median-of-Medians

$A[1..n]$의 원소 $n$개를 5개씩 묶어 $\frac{n}{5}$의 block으로 나눈다.

개수가 안 맞으면 dummy를 붙여 모든 블럭시 5개가 되게 한다. -> $\lceil \frac{n}{5} \rceil$ blocks

각 block의 median 계산(5개 중 3번째)

이 값들을 $M[1..\frac{n}{5}]$에 모은 후 여기서 median을 찾아 pivot으로 사용한다.

 

 

붉은 부분에 주목하자.

median은 주어진 배열에서 $\frac{n}{2}$번째 값이다. 따라서 median을 찾는 과정 역시 Selection이다.

이 과정에서 길이 $m$짜리 배열 $M$에서 $\lceil m/2 \rceil$번째로 작은 값을 찾아낸다.

이게 가능한 이유는 주어진 입력사이즈는 $n$이고 재귀호출하는 사이즈는 $m=\frac{n}{5}$라서

 

 

파란색은 $\frac{n}{5}$개의 블럭들의 중간 블럭의 중간 값이므로 그보다 작은 블럭은 $\frac{n}{10}$개가 있다.

그리고 그 블럭들마다 파란색보다 작은 값이 3개씩 있으므로 총 $\frac{3}{10}n$개의 파란색보다 작은 값(갈색)이 있다.

즉 mom은 적어도 $\frac{n}{10}$개의 블럭보다 크고 $\frac{3}{10}n$개의 값보다 크다

대칭적으로 mom보다 큰 값도 $\frac{3}{10}n$개가 있다.

 

따라서 mom의 랭크 $r$은 $\frac{3}{10}n \;\leq\; r \;\leq\; \frac{7}{10}n$

그리고 이 조건은 goot pivot의 조건에 부합한다.

 

 

Time complexity

Non-recursion part: $O(n)$

Recursion part: $\frac{n}{5}$로 한 번, $\frac{7}{10}n$로 한번

이유는 $\frac{3}{10}n \;\leq\; r \;\leq\; \frac{7}{10}n$을 풀면

$\frac{3}{10}n \;\leq\; n-r \;\leq\; \frac{7}{10}n$라서

 

$\therefore\;\;\;\; T(n) \leq T(n/5) + T(7n/10) + O(n)$

Master theorem 못 써서 Recursion tree 써야 됨

각 level의 합: $n,\;\frac{9}{10}n,\; \frac{81}{100}n,\;$ -> $\frac{9}{10}$씩 줄어든다

$n,\;\frac{9}{10}n,\; \frac{81}{100}n,\;$

$= 1+\frac{9}{10} +(\frac{9}{10})^2+ \cdots + )n$

$=10n$ (무한등비급수)

$=O(n)$