재귀 함수를 분석할 때, 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)를 구하는 전형적인 방법에 대해 알아보겠습니다. 일반적으로 다음 단계를 거쳐 복잡도를 도출할 수 있습니다.
가장 먼저 해야 할 일은 재귀 함수가 어떻게(몇 번) 호출되는지, 그리고 각 호출마다 걸리는 시간이 어느 정도인지 파악하는 것입니다.
함수가 한 번 호출될 때 마다 몇 번의 재귀 호출을 하는가?
각 재귀 호출에서 문제의 크기가 어떻게 변하는가(n→n/2, n→n-1 등)?
재귀 호출 외에 부가적으로 반복문이나 다른 연산(예: 배열을 순회하는 O(n) 작업)이 있는가?
함수 호출 구조를 바탕으로 점화식을 세웁니다. 예를 들어,
단일 호출 예시
T(n)=T(n−1)+O(1)T(n) = T(n-1) + O(1)
이는 “한 번의 함수 호출에서 다시 한 번의 재귀 호출을 하고, 그 외엔 상수 시간이 걸린다”는 뜻입니다.
예: n부터 1까지 순차적으로 내려가며 단순 계산하는 재귀
이진 분할 예시
T(n)=2T(n2)+O(n)T(n) = 2T\Bigl(\frac{n}{2}\Bigr) + O(n)
이는 “한 번의 함수 호출에서 2번의 재귀 호출을 하고, 재귀 호출 외에 O(n) 시간이 걸린다”는 뜻입니다.
예: merge sort, quick sort(평균적으로), binary tree 탐색 등
분할 정복(divide & conquer) 유형
T(n)=a×T(nb)+f(n)T(n) = a \times T\Bigl(\frac{n}{b}\Bigr) + f(n)
여기서 aa는 재귀 호출 횟수, n/bn/b는 입력 크기 분할 비율, f(n)f(n)은 분할/병합 과정에서 드는 부가적인 계산 비용