[Algorithm] 분할정복(1) - Master Theorem과 일반해

🤔 Divide And Conquer

분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다.

 

이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다.

 

이번 포스트에서는 분할정복을 Master Theorem의 일반해를 구하는 방법을 자세하게 알아보겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Master Theorem

Master Theorem에서 Input Size가 $n$일때 분할정복 알고리즘의 일반적인 패턴은 아래와 같습니다.

 

 

 

상수 $a > 0, b > 1, d ≥ 0$에 대하여

1. 문제를 size가 $\frac{n}{b}$인 $a$개의 subproblem으로 나눈다. (recursively 하게)

2. 각각의 subproblem을 해결한 뒤, $O(n^d) 시간을 사용하여 subproblem의 답을 merge한다.

 

 

 

이와 같은 경우 $T(n)$이 문제를 하결하는데 필요한 시간복잡도라고 하면 다음과 같은 식을 얻을 수 있습니다.

 

$$T(n) = aT(\frac{n}{b}) + O(n^d)$$

 

해당 식을 통해 일반해를 얻을 수 있는데 일반해는 아래와 같습니다.

 

 

 

 

그림과 식의 풀이를 통해 위를 증명해보겠습니다.

 

 

 

 

 

 

위의 그림을 통해 각 노드에 해당하는 문제는 $a$개의 subproblem들로 쪼개지며 문제의 크기는 $\frac{1}{b}$배 씩 줄어듭니다.

 

따라서 위의 트리의 높이는 $log_bn$이 됩니다.

 

또한 k번째 level의 노드 수는 최대 $a^k$개이고, 각각의 노드에 해당하는 subproblem의 크기는 $\frac{n}{b^k}$가 됩니다.

 

해당 식의 풀이는 아래와 같습니다.

 

 

 

 

 

 

위와 같이 식을 정리했을 때 식이 등비수열의 형태라는 것을 알 수 있으며 결국 공비인 $\frac{a}{b^d}$의 값에 따라 결과가 달라짐을 알 수 있습니다.

 

이를 통해 $T(n)$의 일반해를 구할 수 있는데 과정은 아래와 같습니다.

 

 

 

 

 

 

위의 일반해를 통해 앞에서 다룬 Merge Sort의 일반해를 바로 구할 수 있습니다.

 

Merge Sort의 경우 기존 문제의 크기를 $\frac{1}{2}$배의 크기인 2개의 subproblem을 분할하는 과정을 거칩니다..

 

즉 $a = 2, b = 2$이며 앞에서 subproblem을 병합하는 데에 걸리는 시간을 $O(n)$이라고 정의 했으므로 $d = 1$는 이라는 정보를 얻을 수 있습니다.

 

이를 Master Theorem에 대입하면 $T(n) = 2T(\frac{n}{2}) + O(n)$의 일반해 $(n) = O(nlogn)$이 됨을 바로 알 수 있습니다.($d = log_ba$의 경우에 해당하므로)