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

Recursion

- Simplify and Delegate

- Reduction

- 종료 조건: Base case

 

Correctness: Induction으로 증명

Time complexity analysis: 점화식부터 구한다

 

 

Divide-and-Conquer

나누고(Divide) 정복한다(Conquer) -> 분할정복

Recursion 활용

 

Ex) Mergesort, Quicksort

 

 

Pattern

분할정복은 일반적으로 다음의 세 단계로 진행된다.

 

① Divide

문제를 나눈다.(Mergesort에서는 2개)

같은 문제의 더 작은 instance로 나눈다.

 

② Delegate (Conquer)

각각의 더 작은 instance에 대해 재귀호출을 한다.

 

③ Combine

Mergesort의 Merge에 해당

 

계속 문제를 나누다 보면 base case에 도달하는데, 이 때는 직접 문제를 풀면 된다.

정렬의 경우 정렬해야 되는 수의 개수가 1개면 할 게 없는데, 이 때가 base case.

-> Combine 단계에서 어떻게 할 지를 고민하면 됨

mergesort의 경우 어떻게 합쳐야 정렬이 될 지를 고민하면 됨

 

 

대부분 Induction으로 증명

Time complexity: 재귀 알고리즘이므로 점화식(recurrence)을 찾는게 우선

 

Ex) Sum

input: $n$

Output: $1 + 2 + 3 + \cdots + n$

 

Iteration: $O(n)$

$s \;\leftarrow\; 0$

$for\; i\; \leftarrow\; 1\; to\; n$

$\;\;\;\; s\; \leftarrow\; s+i$

$return\; s$

 

Recursion: $O(n)$

$if\; n=1\; return\; 1$

$return\; n\; +\; sum2(n-1)$

 

* Recurrence

$T(n) = \begin{cases}1 & (n = 0)\\ 1 + T(n - 1) & (n > 1)\end{cases}\\\rightarrow T(n)=n=O(n)$

 

Divide and Conquer

i) $n$이 짝수라면

$1 + 2 + \cdots + \frac{n}{2} + (\frac{n}{2} + 1) + \cdots + n$

$cf.$ 주어진 문제는 $1$부터 $n$까지의 합이므로 $\frac{n}{2}$ 뒷부분인 $(\frac{n}{2} + 1) + \cdots + n$은 '같은 문제에 대한 instance'가 아니다. 즉 이 부분은 재귀호출로 해결할 수 없다.

앞부분은 됨

 

$1 + 2 + \cdots + \frac{n}{2} + (\frac{n}{2} + 1) + \cdots + n$

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

 

여기서 뒷부분에서 $\frac{n}{2}$를 빼면 $1 + 2 + \cdots + \frac{n}{2}$과 같다는 것을 알 수 있다.

따라서

 

$1 + 2 + \cdots + \frac{n}{2} + (\frac{n}{2} + 1) + \cdots + n$

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

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

-> $sum(\frac{n}{2})$의 값을 구해 2를 곱한 후 $(\frac{n}{2})^2$를 더하면 됨

$sum(\frac{n}{2})$은 원래 문제의 더 작은(절반짜리) instance

 

$n$이 홀수라면

$(1+ \cdots + \frac{n-1}{2}) + (\frac{n-1}{2}+1) + \cdots + n$

$(1+ \cdots + \frac{n-1}{2} + (\frac{n-1}{2}+1) + \cdots + ((\frac{n-1}{2}) + (\frac{n-1}{2}) + n$

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

 

따라서 Pseudocode는

$sum(n)$

$if\; n=1\; return\; 1$

$if\; n\; is\; even\; then$

$\;\;\;\;return\; 2*sum3(n/2) + (n/2)^2$

$else$

$\;\;\;\;return 2*sum((n-1)/2)+((n-1)/2)^2 + n$

 

* Recurrence

$T(n) = \begin{cases}O(1) & (n = 1)\\ 1 + T(\frac{n}{2})  + O(1)& (n > 1)\end{cases}\\\rightarrow T(n)=n=O(n)$

$\rightarrow\; T(n) = O(\log_2{n})$

: 앞의 $O(n)$에 비해 매우 빠름(더 빠른 알고리즘도 있다)

 

시간복잡도에서 $\lfloor \rfloor$같은 건 무시해도 됨. 원래 점화식은 $T(\lfloor \frac{n}{2} \rfloor) + O(1)$

 

Ex) Max

Input: array $A[0..n-1]$

Output: maximum element in $A$

 

- Divide and Conquer

$A$를 반으로 나눠 ($A_1$,$ A_2$) 각각의 최댓값 $m_1$과 $m_2$를 구하면, 둘 중에 더 큰 값이 배열 전체의 최대값이 된다.

 

$max(A[0..n-1]$

$if\; n=1\; return\; A[0]$

$mid\; \leftarrow\; n/2$

$m1\; \leftarrow\; max(A[0..mid])$

$m2\; \leftarrow\; max(A[mid+1..n-1])$

$if\; m1>m2$

$\;\;\;\;then\;return\;m1$

$else\;return\;m2$

 

$T(n) = \begin{cases} O(1) & (n = 1) \\ 2T(\frac{n}{2}) + O(1) \end{cases}$

$\therefore\; T(n) =  O(n)$

비교를 (n-1)보다 적게 하고 최댓값을 찾을 수 없다 -> $O(n)$보다 빠른 알고리즘은 만들 수 없다.

 

 

 

Recursion tree

재귀호출이 이루어지는 과정을 도식화한 것

보통 Tree 형태를 띤다.

처음 호출이 root node가, 재귀호출한 게 자식 노드가 됨

맨 밑의 leaf node가 Base case

 

각 노드의 값은 non-recursive part의 시간복잡도이며 각 노드는 재귀호출만큼의 자식 노드가 생긴다.

따라서 각 노드의 값을 모두 더하면 전체 알고리즘의 running time이 됨

 

Ex) Max

$max(A[0..n-1])$

$if\;\; n=1\; return\; A[0]$

$mid\; \leftarrow\; n/2$

$m1\; \leftarrow\; max(A[0..mid])$

$m2\; \leftarrow\; max(A[mid+1..n-1])$

$if\;\; m1>m2$

$\;\;\;\;then\;\;return\;\;m1$

$else\;\;return\;\;m2$

 

 

 

이 경우 모든 호출에서 연산 횟수가 상수번이므로 시간복잡도는 $C \times (the\;\;number\;\; of\;\; nodes)$가 된다.

Leaf node의 수는 $n$개고, Leaf node의 수는 $n$개인 node의 이진트리의 전체 수는 $n-1 + n = 2n-1$개다.

따라서 시간복잡도는 $C \times (2n - 1) = O(n)$이 된다.

 

 

Ex) Mergesort

Pseudocode for Mergesort

 

재귀호출 부분을 제외하면 $Merge$ 함수 호출 + 1회의 연산이 이루어지며, $Merge$ 함수는 $O(n)$의 시간복잡도를 가진다.

또한 Mergesort의 점화식은 $T(n) = 2T(\frac{n}{2}) + O(n)$이므로 Root node의 value는 cn이 된다.

 

Recursion tree for Mergesort

 

각 계층 별로 노드의 value를 모두 더하면 $cn$이 됨을 알 수 있다. 그리고 포화 이진 트리의 높이는 $\log_2{n}$이므로

시간복잡도는 $cn\log_2{n} = O(n\log{n})$이 된다. (원래는 $cn\lceil \log{n} \rceil$)

 

 

Recursion tree for general Divide-and-Conquer Algorithms

$r$번의 재귀호출 subProblem의 크기가 $n/c$, 재귀호출을 뺀 연산 횟수가 $O(f(n))$이면 점화식은

$T(n) = rT(n/c) + O(f(n))$

이 된다.

 

이 경우 Recursion Tree는 다음과 같다.

A recursion tree for the recurrence $T(n) = rT(n/c) + f(n)$

 

따라서 점화식은 $T(n) = \sum_{i=0}^L r^i \cdot f(n/c^i)$

$L = tree\;\;depth = \log_c{n}$

: 재귀 호출은 $\frac{n}{c^L} = 1$이 될 때까지, 즉 $\log_c{n}=L$이 될 때까지 반복한다.

 

#leaves = $r^L$ = $r^{\log_c{n}}$ = $n^{\log_c{r}}$

 

$f(n)$에 대해서는 다음의 세 가지 경우가 있다.

ⓐ $f(n)$이 $n^{\log_c{r}}$보다 더 빠르게 증가하는 함수일 경우 ($f(n) = \Omega(n^{\log_c{r + \epsilon}})$)

$\;\;then\;\; T(n) = O(f(n))$

   

ⓑ $f(n) = \Theta(n^{\log_c{r}}\log^k{n})\;\;for\;\;k \geq 0$로 표현할 수 있다면

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

 

ⓒ $f(n)$이 $n^{\log_c{r}}$보다 더 느리게 증가하는 함수일 경우($f(n) = O(n^{\log_c{r - \epsilon}})$)

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

 

Master Theorem

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

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

   

ⓑ $If\;\;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})$

 

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

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

 

Ex) $T(n) = 2T(\frac{n}{2}) + O(n)$

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

 

ⓐ $f(n) = \Omega(n^{(1 + \epsilon)})$

ⓑ $f(n) = \Theta(nlog^k{n})$

ⓒ $f(n) = O(n^{(1 - \epsilon)})$

 

ⓐ: $f(n) = n^1$이므로 안 됨($n^1$이 $n^{1.000001}$보다 빠르게 증가하는 함수가 아니니까)

ⓑ $k=0$인 경우 됨 -> $T(n) = O(f(n) \cdot \log{n}) = O(n\log{n})$

ⓒ: ⓐ와 같은 논리로 안 됨 ($n^1$이 $n^{0.999}$보다 느리게 증가하는 함수가 아니니까)

 

 

Ex) $T(n) = T(\frac{n}{2}) + O(n)$

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

$n^{\log_c{r}} = n^0$은 $f(n) = n^1$보다 느리게 증가함 -> ⓒ에 해당함

: $n^r$과 $f(n)$에서의 지수를 비교했을 때 차이가 분명하다면 그를 토대로 ⓐ인지 ⓒ인지 판단할 수 있다.

$\therefore\;\; T(n) = O(f(n)) = O(n)$

 

Ex) $T(n) = T(\frac{n}{2}) + O(1)$

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

$n^{\log_c{r}} = n^0 \approx f(n)=n^0$ -> ⓑ에 해당함

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

 

이 경우 Recursion tree는 선형 트리(자식 노드가 하나인 트리)가 됨

 

Ex) $T(n) = 4T(\frac{n}{2}) + O(n)$

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

$n^{\log_c{r}} = n^2 > f(n)=n^1$ -> ⓒ에 해당함

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

 

 

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

$c = 2$, $r = 3$, $f(n)=n^1$, $1 < \log_c{r} = \log_2{3} = 1.5849625< 2$

$n^{\log_c{r}} = n^{\log_2{3}} > f(n)=n^1$ -> ⓒ에 해당함

$\therefore\;\; T(n) = O(n^{\log_2{3}}) = O(n^{1.5849625})$

 

 

Ex) $T(n) = T(\frac{n}{3}) + O(n^2)$

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

$n^{\log_c{r}} = n^{0} < f(n)=n^2$ -> ⓐ에 해당함

$\therefore\;\; T(n) = O(f(n)) = O(n^2)$

 

 

Ex) $T(n) = 2T(\frac{n}{2}) + O(n\log{n})$

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

$n^{\log_c{r}} = n^{0}$와  $f(n)=n^2$는 지수로 비교 불가 -> ⓑ에 해당함

$\therefore\;\; T(n) = O(f(n)\cdot\log{n}) = O(n\log^2{n})$

 

 

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

이 경우에는 Master theorem을 적용할 수 없다: $T(n) = rT(n/c) + O(f(n))$ 꼴이어야 함

-> Recursion tree로 분석

 

 

Ex) $T(n) = T(n - 2) + T(2) + O(n)$

마찬가지로 Master theorem을 적용할 수 없다. 그냥 해도 됨

 

$T(n) = T(n - 2) + cn + O(n)$: 상수에 대한 $T$ 값은 상수

$T(n) = T(n-4) + c(n - 2) + cn$

$= O(n^2)$

 

 

 

 

재귀 알고리즘에 대한 시간복잡도 분석

알고리즘 명세(슈도코드든 뭐든)를 보고

- subproblem의 size는 어떻게 줄어드는가?

- 몇 번 recursive call 하는가?

- non-recursive work에서 연산의 횟수는 몇 번인가?

를 파악한다.

 

그리고 점화식을 푼다

- Master theorem

- Recursion tree

- Induction

- 저번에 풀었던 거네?

 

 

Mergesort

Pseudocode for Mergesort

recursive call: $\frac{n}{2}$ 크기의 subproblem을 2번

non-recursive: O(n)

-> $T(n) = 2T(\frac{n}{2}) + O(n)$

$\therefore\;\; T(n) = O(n\log{n})$

 

 

Max

$max(A[0..n-1]$

$if\; n=1\; return\; A[0]$

$mid\; \leftarrow\; n/2$

$m1\; \leftarrow\; max(A[0..mid])$

$m2\; \leftarrow\; max(A[mid+1..n-1])$

$if\; m1>m2$

$\;\;\;\;then\;return\;m1$

$else\;return\;m2$

 

$T(n) = 2T(\frac{n}{2}) + O(1) = O(n)$

 

 

Sum

$sum(n)$

$if\; n=1\; return\; 1$

$if\; n\; is\; even\; then$

$\;\;\;\;return\; 2*sum3(n/2) + (n/2)^2$

$else$

$\;\;\;\;return 2*sum((n-1)/2)+((n-1)/2)^2 + n$

 

$T(n) = T(\frac{n}{2}) + O(1) = O(\log{n})$