Recursive Analysis
재귀적 접근 방법 은 알고리즘이 재귀적으로 동작할 때 그 성능을 분석하는 방법이다. 재귀적 알고리즘은 문제를 더 작은 하위 문제로 나누고, 각 하위 문제를 재귀적으로 해결하는 방식으로 동작한다. 재귀적 분석은 하위 문제들이 어떻게 구성되고 합쳐지는지에 따라 전체 성능을 평가하는 데 집중한다.
재귀적 분석의 핵심은 재귀 관계식 을 세우는 것이다. 재귀 관계식은 알고리즘의 실행 시간이나 자원 사용량이 작은 하위 문제들에 의해 어떻게 정의되는지를 나타내는 수식이다. 이를 해결함으로써 알고리즘의 성능을 분석할 수 있다.
점근적 분석은 입력 크기가 매우 클 때 성능을 평가하는 방법이다. 이때는 알고리즘이 어떻게 동작하는지에 대한 세부적인 내용보다는 입력 크기에 따른 전체 성능 경향을 중요하게 다룬다. 예를 들어 $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 에 따른 알고리즘의 실행 시간 또는 자원 사용량을 나타낸다.$$ T(1) \leq c , T(n) \leq 2T\left(\frac{n}{2}\right) + cn $$
이전에 공부했던 merge sort 을 활용해서 재귀적 접근의 여러가지 분석 방법을 공부해보자.
Recursion tree Method은 직접 재귀 상황을 직접 그려보며 분석하는 방법이다. 주어진 input의 사이즈를 계속해서 이분할하며 내려가면 결국 Tree 형태를 가질 것이다. 이때 Runtime을 수동으로 계산해보자!
Divide
Conquer
따라서 $ cn \log_2 n + cn$ 을 BigO 표기법으로 정리하면 Runtime은 다음과 같다.
$$ 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는 모든 하위 문제가 같은 크기일 때 사용되며, Divide와 Conquer 단계에서 발생하는 작업의 상대적인 크기를 비교하여 시간 복잡도를 분석한다.
Master Method는 다음과 같은 형태의 재귀 관계식에 적용된다.
$$ T(n) = aT\left(\frac{n}{b}\right) + f(n) $$
이때, 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)$ 가 된다. 이는 병합 정렬의 시간 복잡도를 잘 설명해준다.
위 방법에서 $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 $$