재귀함수의 시간복잡도를 분석하는 것은 조금 까다로울 수 있지만, 몇 가지 일반적인 접근 방법을 통해 체계적으로 분석할 수 있습니다. 다음은 재귀함수의 시간복잡도를 분석하는 일반적인 단계입니다.
1. 재귀 관계식 세우기
재귀함수의 시간복잡도를 분석하려면 먼저 함수의 실행 시간에 대한 재귀 관계식을 세워야 합니다. 이 재귀 관계식은 함수가 호출될 때마다 얼마나 많은 시간이 걸리는지를 나타냅니다.
예를 들어, 피보나치 수열을 계산하는 간단한 재귀함수를 생각해봅시다.
int fib(int n) {
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}이 함수의 시간복잡도 T(n)은 다음과 같은 재귀 관계식을 따릅니다:
[ T(n) = T(n-1) + T(n-2) + O(1) ]
여기서 O(1)은 함수 호출 자체에 소요되는 시간입니다.
2. 초기 조건 찾기
다음 단계는 기저 조건에 대한 시간복잡도를 찾는 것입니다. 위의 예제에서는 n이 0 또는 1일 때, 시간복잡도는 O(1)입니다.
3. 마스터 정리 또는 재귀 관계 해결하기
재귀 관계식을 해결하는 여러 가지 방법이 있습니다. 가장 널리 사용되는 방법은 마스터 정리(Master Theorem)를 사용하는 것입니다. 하지만, 모든 재귀 관계식에 마스터 정리를 적용할 수 있는 것은 아닙니다. 이러한 경우, 반복 대치법(iterative substitution)이나 재귀 트리(recursion tree) 방법을 사용할 수 있습니다.
마스터 정리
마스터 정리는 다음과 같은 형태의 재귀 관계식을 해결할 때 유용합니다:
[ T(n) = aT\left(\frac{n}{b}\right) + f(n) ]
여기서 a, b는 상수이고, f(n)은 n에 대한 함수입니다. 마스터 정리에 따르면, f(n)의 성장 속도에 따라 세 가지 경우로 나눌 수 있습니다:
- Case 1: ( f(n) = O(n^c) )이고, ( c < \log_b{a} )
- [ T(n) = \Theta(n^{\log_b{a}}) ]
- Case 2: ( f(n) = \Theta(n^{\log_b{a}}) )
- [ T(n) = \Theta(n^{\log_b{a}} \log{n}) ]
- Case 3: ( f(n) = \Omega(n^c) )이고, ( c > \log_b{a} )
- [ T(n) = \Theta(f(n)) ]
피보나치 수열의 경우는 마스터 정리를 적용할 수 없기 때문에, 반복 대치법이나 재귀 트리 방법을 사용해야 합니다.
반복 대치법
반복 대치법은 재귀 관계식을 반복해서 대치하여 일반적인 형태로 변환하는 방법입니다.
예를 들어, 피보나치 수열의 경우:
[ T(n) = T(n-1) + T(n-2) + O(1) ]
이것을 반복적으로 대치하면, 지수 함수 형태로 증가하는 것을 알 수 있습니다. 따라서, 피보나치 수열의 재귀적 시간복잡도는 ( O(2^n) )입니다.
재귀 트리
재귀 트리 방법은 재귀 호출을 트리 형태로 시각화하여 각 레벨에서의 호출 수와 각 호출의 비용을 계산하는 방법입니다.
예를 들어, 피보나치 수열의 경우:
- 최상위 호출이 ( T(n) )
- 두 개의 하위 호출이 각각 ( T(n-1) )과 ( T(n-2) )
- 각각의 하위 호출도 동일한 패턴을 따름
이렇게 트리를 그리면, 총 노드 수가 지수적으로 증가하는 것을 확인할 수 있습니다.
4. 최종 시간복잡도 결론
이러한 단계를 통해 최종 시간복잡도를 도출할 수 있습니다. 앞서 예로 든 피보나치 수열 재귀함수의 시간복잡도는 ( O(2^n) )입니다. 반면, 동적 계획법을 사용한 피보나치 수열의 시간복잡도는 ( O(n) )입니다.
예시: 병합 정렬
병합 정렬의 재귀 관계식을 통해 분석해봅시다.
void mergeSort(int arr[], int l, int r) {
if (l >= r)
return;
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}여기서 병합 함수는 O(n)의 시간복잡도를 가집니다.
재귀 관계식은 다음과 같습니다:
[ T(n) = 2T\left(\frac{n}{2}\right) + O(n) ]
이것은 마스터 정리의 두 번째 경우에 해당합니다 (( f(n) = \Theta(n) ), ( \log_b{a} = \log_2{2} = 1 )). 따라서 병합 정렬의 시간복잡도는 ( O(n \log{n}) )입니다.
위의 단계를 통해 재귀함수의 시간복잡도를 체계적으로 분석할 수 있습니다.