알고리즘의 재귀적 분석

1. 재귀적 접근 방법

Recursive Analysis

재귀적 접근 방법 은 알고리즘이 재귀적으로 동작할 때 그 성능을 분석하는 방법이다. 재귀적 알고리즘은 문제를 더 작은 하위 문제로 나누고, 각 하위 문제를 재귀적으로 해결하는 방식으로 동작한다. 재귀적 분석은 하위 문제들이 어떻게 구성되고 합쳐지는지에 따라 전체 성능을 평가하는 데 집중한다.

재귀적 분석의 핵심은 재귀 관계식 을 세우는 것이다. 재귀 관계식은 알고리즘의 실행 시간이나 자원 사용량이 작은 하위 문제들에 의해 어떻게 정의되는지를 나타내는 수식이다. 이를 해결함으로써 알고리즘의 성능을 분석할 수 있다.

1-2. 재귀적 분석과 점근적 분석의 차이점

점근적 분석은 입력 크기가 매우 클 때 성능을 평가하는 방법이다. 이때는 알고리즘이 어떻게 동작하는지에 대한 세부적인 내용보다는 입력 크기에 따른 전체 성능 경향을 중요하게 다룬다. 예를 들어 $O(n^2)$, $O(n \log n)$ 등의 표현을 통해 성능을 추상적으로 표현한다.

재귀적 분석은 알고리즘의 재귀적 구조에 집중한다. 알고리즘이 재귀적으로 문제를 해결할 때 하위 문제로 나뉘는 과정과 그에 따른 재귀 호출의 실행 시간을 구체적으로 분석한다. 주로 어떤 n번째 시퀸스의 값은 n - 1 시퀸스와 n - 2 시퀸스의 합으로 이루어진다. 즉 수식으로 표현하면 아래와 같다.

그러나 이런 점화식 표현은 읽기 어렵기 때문에 일반 Runtime 표기법과 비슷하게 바꿔주는 과정이 필요하다.

1-3. 재귀 관계식의 구조

재귀 관계식은 보통 다음과 같은 형태로 표현된다.

• $T(n)$ 은 입력 크기 n 에 따른 알고리즘의 실행 시간 또는 자원 사용량을 나타낸다.
• $a$ 는 문제를 몇 개의 하위 문제로 나누는지를 나타낸다.
• $\frac{n}{b}$는 각 하위 문제의 크기를 나타낸다. 여기서$b$ 는 문제를 나눌 때 입력 크기를 몇 배 줄이는지를 나타낸다.
• $O(n^d)$는 하위 문제들을 나누고 다시 합치는 데 필요한 추가 작업을 나타낸다. 여기서$d$ 는 이러한 추가 작업의 복잡도를 나타낸다.

merge sort의 점화식

$$T(1) \leq c , T(n) \leq 2T\left(\frac{n}{2}\right) + cn$$

이전에 공부했던 merge sort 을 활용해서 재귀적 접근의 여러가지 분석 방법을 공부해보자.

2. Recursion tree Method

Recursion tree Method은 직접 재귀 상황을 직접 그려보며 분석하는 방법이다. 주어진 input의 사이즈를 계속해서 이분할하며 내려가면 결국 Tree 형태를 가질 것이다. 이때 Runtime을 수동으로 계산해보자!

2-1. Runtime 분석

• Divide
  • $ cn \log_2 n$
  • 트리 마지막 노드까지 내려가는 비용
• Conquer
  • $cn$
  • 각 배열을 비교하고 합치는 것은 Linear Time 안에 가능

따라서 $ cn \log_2 n + cn$ 을 BigO 표기법으로 정리하면 Runtime은 다음과 같다.

$$O(n logn)$$

3. Iteration Method

Iteration Method는 재귀적 관계식을 반복적으로 확장하여 하나의 패턴을 찾아내는 방법이다. 이를 통해 재귀적으로 정의된 알고리즘의 성능을 분석할 수 있다. merge sort의 재귀 관계식은 다음과 같다.

여기서, $T(n)$은 항상 $2T\left(\frac{n}{2}\right) + cn$보다 같거나 작다는 것을 알 수 있다. 따라서 우리는$T(n)$을 이 식을 이용하여 분석할 수 있다. 이 식은 재귀적으로 표현된 알고리즘의 실행 시간을 나타내므로, 이를 반복적으로 확장하여 성능을 분석하는 것이다.

3-1. 재귀 관계식 확장

재귀 관계식을 여러 번 확장하여 패턴을 찾아본다. 우선, $T\left(\frac{n}{2}\right)$ 을 구하기 위해 해당 값을 대입해보자:

이 식을 $T(n)$에 대입하면,

이 과정을 반복하면 다음과 같은 패턴을 찾을 수 있다!

3-2. k의 의미

여기서 $k$는 배열을 이분할하는 횟수를 의미한다. 즉, 배열의 크기를 계속 2로 나누어 1이 될 때까지의 단계를 나타낸다. 배열의 크기$n$ 을 1로 나누는 데 필요한 횟수는 $\log_2 n$ 이다. 따라서 $k = \log_2 n$이 된다.

3-3. Runtime 분석

위에서 구한 관계식에 $k = \log_2 n$ 을 대입하면 다음과 같다.

이를 간단히 해보자.

여기서 $T(1) \leq c$ 이므로, 이를 대입하면 최종적으로 다음과 같은 식을 얻게 된다.

따라서 병합 정렬의 시간 복잡도는,

$$T(n) = O(n \log n)$$

3-4. 결론

Iteration Method를 통해 병합 정렬의 재귀적 관계식을 확장하고 패턴을 찾아 시간 복잡도를 구할 수 있다. 최종적으로 병합 정렬의 시간 복잡도는 $O(n \log n)$ 이다. 이는 입력 배열을 분할하는 단계와 병합하는 단계가 각각 $O(\log n)$과$O(n)$에 비례하기 때문에, 전체 시간 복잡도는 두 단계의 곱인$O(n \log n)$으로 나타난다.

4. Master Method

우리의 목표는 최종적으로 재귀 관계식을 시간 복잡도 로 추상화하는 것이다. 이 과정에서 Master Method 는 특정한 형태의 재귀식에 대해 시간 복잡도를 계산할 수 있는 도구이다. 특히, Master Method는 모든 하위 문제가 같은 크기일 때 사용되며, Divide와 Conquer 단계에서 발생하는 작업의 상대적인 크기를 비교하여 시간 복잡도를 분석한다.

4-1. 기본 가정

Master Method는 다음과 같은 형태의 재귀 관계식에 적용된다.

• $a \geq 1$, $b > 1$ 은 상수이다.
• $f(n)$ 은 asymptotically positive인 함수로, 즉 입력 크기가 충분히 클 때 양수가 되는 함수이다.

4-2. Divide와 Conquer

• Master Method에서는 재귀식의 두 주요 부분인 Divide와 Conquer를 비교한다.
• Divide는 문제를 나누는 단계로, $a$개의 하위 문제를 생성하는데 각 하위 문제의 크기는$\frac{n}{b}$ 이다.
• Conquer는 하위 문제를 해결하고 이를 다시 병합하는 과정으로, 병합하는 데 걸리는 시간은 $f(n)$ 으로 표현된다.

이때, Divide 부분에서 발생하는 전체 작업량은 $n^{\log_b a}$ 로 계산할 수 있다. 이것은 문제를 나누는 데 필요한 연산 양을 의미한다.

• $n^{\log_b a}$ : 재귀 호출을 통해 나누어진 하위 문제들의 시간 복잡도를 의미한다.
• $f(n)$ : 병합 과정에서 수행되는 연산의 시간 복잡도를 나타낸다.

4-3. 세 가지 경우의 분석

Master Method는 $f(n)$과$n^{\log_b a}$ 를 비교하여 세 가지 경우로 나뉜다.

1. $f(n) = \Theta(n^{\log_b a})$

   • 이 경우, 하위 문제를 나누고 해결하는 데 걸리는 시간과 병합하는 데 걸리는 시간이 동일하다.
   • 이때 전체 시간 복잡도는 $T(n) = \Theta(n^{\log_b a} \log n)$ 가 된다. (여기서 로그 항은 병합 단계의 추가 비용 의미)

2. $f(n) = \Omega(n^{\log_b a + \epsilon})$ (for a constant $\epsilon > 0$)

   • 이 경우, 병합 과정에서의 연산이 더 많은 시간 복잡도를 차지한다.
   • 따라서 전체 시간 복잡도는 $T(n) = \Theta(f(n))$ 가 된다. 즉, 병합 과정이 지배적이므로 병합의 시간 복잡도가 최종적인 시간 복잡도가 된다.

3. $f(n) = O(n^{\log_b a - \epsilon})$ (for a constant $\epsilon > 0$)

   • 이 경우, 하위 문제를 나누고 해결하는 데 걸리는 시간이 더 많은 연산을 필요로 한다.
   • 따라서 전체 시간 복잡도는 $T(n) = \Theta(n^{\log_b a})$ 가 된다.

4-4. Master Method 예시

병합 정렬(merge sort)의 재귀식은 다음과 같다.

여기서:

• $a = 2$,$b = 2$
• $f(n) = O(n)$
• $n^{\log_b a} = n^{\log_2 2} = n$

따라서 이 식은 첫 번째 경우에 해당한다. 이 경우 전체 시간 복잡도는 $O(n \log n)$ 가 된다. 이는 병합 정렬의 시간 복잡도를 잘 설명해준다.

5. Master Method (specific ver)

위 방법에서 $f(n)$이$n^d$, 즉 n의 d차식으로 표현되는 경우 조금 더 간단하게 판별할 수 있다.

• $a$ 는 하위 문제의 개수를 나타낸다.
• $b$ 는 입력 크기가 얼마나 줄어드는지를 나타낸다.
• $d$ 는 각 하위 문제를 처리하기 위해 필요한 추가 작업의 복잡도를 나타낸다.

$a = b^d$

• Divide 단계와 Conquer 단계가 동일한 크기의 작업을 요구하는 경우이다.
• 이 경우는 문제를 나누는 과정과 병합하는 과정이 균형을 이루는 상황에 해당한다.

$a > b^d$

• Divide에서 더 많은 작업이 발생하는 경우이다.
• 이 경우는 주로 하위 문제의 수가 많아지면서 문제가 Divide에서 더 많은 연산을 요구하는 상황이다.

$a < b^d$

• Conquer에서 더 많은 작업이 발생하는 경우이다.
• 이 경우는 병합 단계에서 더 많은 연산이 요구되며, 병합 과정이 시간 복잡도를 지배한다.

5-2. Master Method 예시

이번에도 병합정렬을 예시로 분석해보자.

• $a = 2$ (하위 문제의 개수),
• $b = 2$ (입력 크기가 2로 나누어짐),
• $d = 1$ (병합하는 데 걸리는 시간은 O(n))이다.

이를 Master Method에 적용하면, $a = b^d$ 이므로 case 1에 해당한다. 따라서 병합 정렬의 시간 복잡도는!

$$O(n logn)$$

5-3. 연습

아래 예시들을 통해 더 연습해보자