Master theorem

Divide-and-Conquer 문제는, n size의 문제를 a개의 size n/b subproblem으로 나누고, 재귀적으로 풀어나가는 패턴을 취합니다. 그리고 합치는데 $O(n^{d})$ 시간이 걸린다고 하죠. 이 때의 running time을 다음과 같이 나타낼 수 있습니다.

 

Master theorem: $T(n) = aT([n/b]) + O(n^{d}), \ where \ a, b, d > 0$

궁극적으로 분할정복을 사용했을 때 T(n)이 어떻게 계산되는지를 알고 싶은데, 다음과 같이 3가지 경우가 존재합니다.

1. $T(n) = O(n^{d}), \ if \ d > log_{b}a$
2. $T(n) = O(n^{d}logn), \ if \ d = log_{b}a$
3. $T(n) = O(n^{log_{b}a}), \ if \ d < log_{b}a$

몇 가지 분할정복 알고리즘 예시를 통해 master theorem을 적용시켜 시간복잡도를 구해 봅시다.

 

1. Merge sort

먼저, 분할정복 알고리즘을 사용한 대표적인 예시인 merge sort를 통해 알아봅시다. Merge sort는 n개의 숫자들을 더 이상 나눌 수 없을 때까지 2개의 부분문제로 분할하고, 2개씩 합쳐가면서 정렬하는 알고리즘입니다. 다음 이미지는 위키백과에 있는 merge sort를 시각화한 것입니다.

출처: 위키백과

n개의 문제를, 매 단계에서 n/2 크기의 2개의 subproblem으로 분리합니다. 2개의 부분문제를 합칠때 걸리는 시간은 $O(n)$입니다. 즉, a=2, b=2, d=1인 경우입니다. Master theorem의 2번 케이스에 해당되는 경우입니다.($1 = log_{2}{2}$) 흔히 알고있는 merge sort의 시간복잡도인 $O(n^{1}logn)$이 나오는 것을 확인할 수 있습니다.

 

 

2. Matrix multiplication

다음으로는 효율적인 matrix multiplication을 봅시다. n*n matrix X, Y, Z가 있고, Z = XY 관계라고 합시다. 이 때 Z의 각 element는 $Z_{ij} = \sum_{k=1}^{n}X_{ik}Y_{kj}$로 나타낼 수 있습니다. 총 $n^{2}$개의 element를 구해야 하는데 각 element 계산하는데 $O(n)$이 걸리니까 일반적인 연산으로 총 걸리는 시간은 $O(n^{3})$입니다. 이를, 분할정복 알고리즘을 통해 효율적으로 계산해봅시다.

 

먼저, matrix X, Y를 다음과 같이 4 부분으로 나눠줍니다.

 

$ X = \begin{bmatrix} A & B \\ C  & D \end{bmatrix}$,  $\ Y = \begin{bmatrix} E & F \\ G  & H \end{bmatrix}$

 

그러면, Z = XY는 다음과 같이 나타낼 수 있습니다.

 

$ XY = \begin{bmatrix} AE+BG & AF+BH \\ CE+DG  & CF+DH \end{bmatrix}$

 

2개의 subelement(AE, BG, etc.)를 더하는데는 $O((n/2)^2) = O(n^2)$가 소요됩니다. 즉, 이렇게 문제를 나눠서 생각할 경우 재귀 관계식은 다음과 같이 나타낼 수 있습니다.

 

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

 

a=8, b=2, d=2이므로, $2 < log_{2}3 = 3$이니까, 결국, $\ O(n^{3})$시간임은 변하지 않습니다. 하지만, 각 subelement 계산을 효율적으로 할 수 있는 방법이 있습니다. 다음과 같이 7개의 part를 만들어봅시다.

 

$P_{1} = A(F-H) \quad P_{2} = (A+B)H \quad P_{3} = (C+D)E \quad P_{4} = D(G-E)$

 

$P_{5} = (A+D)(E+H) \quad P_{6} = (B-D)(G+H) \quad P_{7} = (A-C)(E+F)$

 

그러면, 위 7개 part를 이용해서 XY를 다시 다음과 같이 쓸 수 있습니다.

 

$ XY = \begin{bmatrix} P_{5}+P_{4}-P_{2}+P_{6} & P_{1}+P_{2} \\ P_{3}+P_{4}  & P_{1}+P_{5}-P_{3}-P_{7} \end{bmatrix}$

 

그러면 기존 8개가 아닌 7개의 $T(n/2)$ 연산(행렬곱)만 수행하면 되고, 전체 $T(n)$은 다음과 같이 나타낼 수 있습니다.

 

$T(n) = 7T(n/2) + O(n^{2})$

 

그럼, $O(n^{3})$ 대신 $O(n^{log_{2}7})$이 되고, $O(n^{2.81})$ 정도로 단축시킬 수 있습니다.

 

 

직관적으로 보면, 문제를 어떤 사이즈로 몇 개로 나누는가, 그리고 나눈 문제를 합치는데 얼마나 시간이 걸리는가에 의해 분할정복 알고리즘 전체 시간이 결정된다고 생각하면 됩니다. 문제를 n/b 사이즈로 더 이상 나눌 수 없을 때까지 나눌 때, tree처럼 생각하면 $log_{b}n$ level이 생기고, 각 level마다 생기는 문제가 a개니까 $a^{log_{b}n} = n^{log_{b}a}$ 시간이 걸린다고 생각할 수 있습니다. 그 외에 부분문제를 합치는 시간인 $O(n^{d})$를 더해야 하니 총 시간을 $O(n^{d}) + O(n^{log_{b}a})$로 나타낼 수 있고, n의 지수 부분이 큰 쪽으로 시간복잡도가 결정된다고 생각할 수 있습니다.

 

이렇게 문제가 어떻게 분할되는지, 합치는데 얼마나 걸리는지 알고 있다면, master theorem을 통해 시간 복잡도를 간편하게 계산할 수 있습니다.