![Featured Image for [알고리즘] 재귀적 분석](https://ih1.redbubble.net/image.1502642451.8092/st,small,507x507-pad,600x600,f8f8f8.jpg)
재귀적 접근 방법(recursive analysis)은 알고리즘이 재귀적으로 동작할 때 그 성능을 분석하는 방법이다. 재귀적 알고리즘은 문제를 더 작은 하위 문제로 나누고, 각 하위 문제를 재귀적으로 해결하는 방식으로 동작한다. 재귀적 분석은 하위 문제들이 어떻게 구성되고 합쳐지는지에 따라 전체 성능을 평가하는 데 집중한다.
재귀적 분석의 핵심은 **재귀 관계식(recurrence relation)**을 세우는 것이다. 재귀 관계식은 알고리즘의 실행 시간이나 자원 사용량이 작은 하위 문제들에 의해 어떻게 정의되는지를 나타내는 수식이다. 이를 해결함으로써 알고리즘의 성능을 분석할 수 있다.
점근적 분석은 입력 크기가 매우 클 때 성능을 평가하는 방법이다. 이때는 알고리즘이 어떻게 동작하는지에 대한 세부적인 내용보다는 입력 크기에 따른 전체 성능 경향을 중요하게 다룬다. 예를 들어 $O(n^2)$, $O(n \log n)$ 등의 표현을 통해 성능을 추상적으로 표현한다.
재귀적 분석은 알고리즘의 재귀적 구조에 집중한다. 알고리즘이 재귀적으로 문제를 해결할 때 하위 문제로 나뉘는 과정과 그에 따른 재귀 호출의 실행 시간을 구체적으로 분석한다. 주로 어떤 n번째 시퀸스의 값은 n - 1 시퀸스와 n - 2 시퀸스의 합으로 이루어진다. 즉 수식으로 표현하면 아래와 같다.
$$ T(n) = T(n - 1) + T(n - 2) $$
그러나 이런 점화식 표현은 읽기 어렵기 때문에 일반 Runtime 표기법과 비슷하게 바꿔주는 과정이 필요하다.
재귀 관계식은 보통 다음과 같은 형태로 표현된다.
$$ T(n) = a \cdot T\left(\frac{n}{b}\right) + O(n^d) $$
n 에 따른 알고리즘의 실행 시간 또는 자원 사용량을 나타낸다.이전에 공부했던 merge sort 의 점화식을 대상으로 분석해보자!
merge sort의 점화식
$$ T(1) \leq c , T(n) \leq 2T\left(\frac{n}{2}\right) + cn $$
Recursion tree Method은 직접 재귀 상황을 직접 그려보며 분석하는 방법이다. 주어진 input의 사이즈를 계속해서 이분할하며 내려가면 결국 Tree 형태를 가질 것이다. 이때 Runtime을 수동으로 계산해보자!
따라서 $ cn \log_2 n + cn$ 을 BigO 표기법으로 정리하면 다음과 같다.
$$ O(n logn) $$
Iteration Method는 재귀적 관계식을 반복적으로 확장하여 하나의 패턴을 찾아내는 방법이다. 이를 통해 재귀적으로 정의된 알고리즘의 성능을 분석할 수 있다. 병합 정렬(merge sort)의 재귀 관계식은 다음과 같다:
$$ T(1) \leq c, \quad T(n) \leq 2T\left(\frac{n}{2}\right) + cn $$
여기서, $T(n)$은 항상 $2T\left(\frac{n}{2}\right) + cn$ 보다 같거나 작다는 것을 알 수 있다. 따라서 우리는 $T(n)$을 이 식을 이용하여 분석할 수 있다. 이 식은 재귀적으로 표현된 알고리즘의 실행 시간을 나타내므로, 이를 반복적으로 확장하여 성능을 분석하는 것이다.
재귀 관계식을 여러 번 확장하여 패턴을 찾아본다. 우선, $T\left(\frac{n}{2}\right)$ 을 구하기 위해 해당 값을 대입해보자:
$$ T\left(\frac{n}{2}\right) = 2T\left(\frac{n}{4}\right) + \frac{cn}{2} $$
이 식을 $ T(n) $에 대입하면,
$$ T(n) \leq 2\left(2T\left(\frac{n}{4}\right) + \frac{cn}{2}\right) + cn = 4T\left(\frac{n}{4}\right) + 2cn $$
이 과정을 반복하면 다음과 같은 패턴을 찾을 수 있다!
$$ T(n) \leq 2^k T\left(\frac{n}{2^k}\right) + kcn $$
여기서 $k$ 는 배열을 이분할하는 횟수를 의미한다. 즉, 배열의 크기를 계속 2로 나누어 1이 될 때까지의 단계를 나타낸다. 배열의 크기 $n$ 을 1로 나누는 데 필요한 횟수는 $\log_2 n$ 이다. 따라서 $k = \log_2 n$이 된다.
위에서 구한 관계식에 $k = \log_2 n$ 을 대입하면 다음과 같다.
$$ T(n) \leq 2^{\log_2 n} T\left(\frac{n}{2^{\log_2 n}}\right) + cn \log_2 n $$
이를 간단히 해보자.
$$ T(n) \leq nT(1) + cn \log_2 n $$
여기서 $T(1) \leq c$ 이므로, 이를 대입하면 최종적으로 다음과 같은 식을 얻게 된다.
$$ T(n) \leq cn + cn \log_2 n $$
따라서 병합 정렬의 시간 복잡도는,
$$ T(n) = O(n \log n) $$
Iteration Method를 통해 병합 정렬의 재귀적 관계식을 확장하고 패턴을 찾아 시간 복잡도를 구할 수 있다. 최종적으로 병합 정렬의 시간 복잡도는 $ O(n \log n) $ 이다. 이는 입력 배열을 분할하는 단계와 병합하는 단계가 각각 $O(\log n)$ 과 $O(n)$ 에 비례하기 때문에, 전체 시간 복잡도는 두 단계의 곱인 $O(n \log n)$으로 나타난다.
우리의 목표는 최종적으로 재귀 관계식을 시간 복잡도로 추상화하는 것이다. 이 과정에서 Master Method 는 특정한 형태의 재귀식에 대해 시간 복잡도를 계산할 수 있는 도구이다. 특히, Master Method는 모든 하위 문제(sub-problems)가 같은 크기일 때 사용되며, Divide와 Conquer 단계에서 발생하는 작업의 상대적인 크기를 비교하여 시간 복잡도를 분석한다.
Master Method는 다음과 같은 형태의 재귀 관계식에 적용된다.
$$ T(n) = aT\left(\frac{n}{b}\right) + f(n) $$
여기서:
Master Method에서는 재귀식의 두 주요 부분인 Divide와 Conquer를 비교한다.
이때, Divide 부분에서 발생하는 전체 작업량은 $n^{\log_b a}$ 로 계산할 수 있다. 이것은 문제를 나누는 데 필요한 연산 양을 의미한다.
Master Method는 $f(n)$ 과 $n^{\log_b a}$ 를 비교하여 세 가지 경우로 나뉜다.
$f(n) = \Theta(n^{\log_b a})$
$f(n) = \Omega(n^{\log_b a + \epsilon})$ (for a constant $\epsilon > 0$)
$f(n) = O(n^{\log_b a - \epsilon})$ (for a constant $\epsilon > 0$)
병합 정렬(merge sort)의 재귀식은 다음과 같다:
$$ T(n) = 2T\left(\frac{n}{2}\right) + O(n) $$
여기서:
따라서 이 식은 첫 번째 경우에 해당한다. 이 경우 전체 시간 복잡도는 **$O(n \log n)$ **가 된다. 이는 병합 정렬의 시간 복잡도를 잘 설명해준다.
Master Method는 특정 형태의 재귀식을 효율적으로 해결하는 도구로, 세 가지 경우로 나뉘어 Divide와 Conquer의 상대적인 크기를 분석한다. 이를 통해 재귀 관계식을 시간 복잡도로 변환할 수 있으며, 알고리즘의 성능을 분석하는 데 매우 유용하다.
위 방법에서 $f(n)$ 이 $n^d$, 즉 n의 d차식으로 표현되는 경우 조금 더 간단하게 판별할 수 있다.
여기서:
$$ T(n) = O(n^d \log n) \quad \text{if } a = b^d $$
$$ T(n) = O(n^d) \quad \text{if } a < b^d $$
$$ T(n) = O(n^{\log_b a}) \quad \text{if } a > b^d $$
이번에도 병합정렬을 예시로 분석해보자.
$$ T(n) = 2T\left(\frac{n}{2}\right) + O(n) $$
이를 Master Method에 적용하면, $a = b^d$ 이므로 case 1에 해당한다. 따라서 병합 정렬의 시간 복잡도는 다음과 같다:
$$ O(n logn) $$
아래 예시들을 통해 더 연습해보자
$$ T(n) = T\left(\frac{n}{2}\right) + n $$
$$ T(n) = 2 \cdot T\left(\frac{n}{2}\right) + n $$
$$ T(n) = 4 \cdot T\left(\frac{n}{2}\right) + n $$