Overview

Divide-and-Conquer, 이 알고리즘은 여러 알고리즘의 기본이 되는 알고리즘이다. 대표적인 예시로 Merge Sort와 같은 여러가지 Sorting Algorithm과 음성 데이터를 분석할 때 필수적으로 진행하는 Fast Fourier Transform(FFT) 등이 있다. 해당 페이지에서는 Merge Sort를 예시로 설명한다.

Divide-and-Conquer Algorithm

Divide-and-Conquer Algorithm(분할 정복 알고리즘)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘이다. 보통 재귀 함수를 통해 구현된다.

• Divede: 입력 데이터 $S$를 서로 겹치지 않는 부분 집합으로 분할한다.$(S_1, S_2, …)$
• Recur: 분할하여 생성된 sub-problem(하위 문제)을 재귀적으로 해결한다.
• Conquer: $(S_1, S_2, …)$의 Solution을 결합하여 $S$의 Solution을 얻는다.

Recurrence Equation Analysis

Merge sort의 Conquer 단계는 두 개의 정렬된 시퀀스 각각 $N/2$개의 요소로 구성된 이중 연결 리스트를 병합하는 것이다. 일부 상수 $b$에 대해 최대 $bN$ 단계를 가진다. Merge sort의 실행 시간을 $T(n)$이라고 하면, Recurrence Equation(재귀식)은 다음과 같다.

$T(N) = \begin{cases} b &\text{if }N < 2\\ 2T(N/2) + bN &\text{if }N ≥ 2 \end{cases}$

Iterative Substitution

Iterative Substitution을 통해 재귀식을 반복적으로 적용하여 패턴을 찾아낸다.

$\begin{aligned} T(N) &= 2T(N/2) + bN\\ &=2(2T(N/2^2) + b(N/2)) + bN\\ &=2^2T(N/2^2) + 2bN\\ &=2^3T(N/2^3) + 3bN\\ &=...\\ &=2^iT(N/2^i) + ibN \end{aligned}$

Base case인 $T(N) = b$는 $2^i = N$일 때 만족한다. 즉, $i=\log N$이다.

따라서 $T(N) = N\log N + bN$이므로 $T(N) = O(N\log N)$이다.

The Recursion Tree

The Recursion Tree는 재귀 관계를 시각화함으로써 패턴을 파악할 때 도움을 준다.

Guess-and-Test Method

Guess-and-Test Method는 closed form solution을 추측하고 induction으로 증명하는 방법이다.