[알고리즘] 재귀 트리 Recursion Tree

T(n)의 복잡도를 추정하기 위해, 즉 알고리즘의 시간복잡도를 모델링하기 위해서 재귀트리를 사용합니다.

재귀트리를 이용해 시간복잡도를 구하기 위해서는 점화식이 필요한데,

점화식을 다양한 높이의 재귀호출에서 발생할 비용을 나타내는 노드가 있는 트리 구조로 변환합니다.

시간 복잡도를 구하기 위해 높이와 층별 노드합을 구해야 하는데,

높이는 n층에서의 일반항을 구해 나타내며(필기 참조), 노드합은 하나의 깊이에서 노드를 모두 더해 나타냅니다.

 

계수가 같고 합이 일정한 경우

점화식이 T(n) = 2T(n/2) + cn의 꼴이므로

T(n)은 호출 시마다 2개의 T(n/2)를 호출합니다.

따라서 트리가 그림과 같이 그려지게 되고, 각 층의 노드합은 cn이 되며, 

그러므로 O(nlogn)의 시간복잡도를 가지게 됩니다.

 

계수가 다르고 합이 일정한 경우

전반적으로 1번과 유사합니다.

다만, 1번의 경우 같은 계수의 재귀호출이 일어났지만 2번의 경우는 다른 계수를 가지는 재귀함수가 호출이 되는데,

재귀 트리는 시간 복잡도를 구하는 과정이므로 계수가 더 큰 쪽을 택해 높이로 변환해줍니다.

마찬가지로 합이 일정한 경우이기 때문에 각 층의 노드합은 cn이 되어 

O(nlogn)의 시간복잡도를 가집니다.

 

계수가 같고 합이 일정하지 않은 경우

지금까지는 같은 깊이 노드합이 같은 경우만 봤지만, 이처럼 각 층의 노드합이 등비수열 꼴로 다르게 나타나는 경우가 있습니다.

이럴때는 바로 구할 수 있는 높이와 각 층의 노드합을 구해봅니다.

각 층의 노드 합을 구했을 때, 깊이 n에서 노드합을 유추해봅니다.

노드의 개수를 보면, 층마다 3^n 꼴로 노드의 수가 증가하는 것을 볼 수 있습니다.

그러므로 최종 log_4(n)에서의 노드의 개수는 n^(log_4(3))이 되는 것을 확인할 수 있습니다.

이제 T(n)을 일반항으로 나타내고, 등비수열의 합을 이용해 식을 구해준 다음, upper bound를 다루는 빅오표기법을 이용해 등비수열의 극한으로 해결하면 편하게 구할 수 있습니다.

그러므로, T(n) = 3T(n/3) + cn^2의 시간복잡도는 O(n^2)임을 확인할 수 있습니다.

 

계수가 다르고 합이 일정하지 않은 경우

3번의 경우와 크게 다르지 않습니다.

높이의 값을 계수가 큰 값으로 따라가고, 역시 등비수열을 이용해 시간복잡도를 구할 수 있습니다.

 

참고 : 다양한 점화식의 시간복잡도