[Algorithm] 재귀 트리(Recursion Tree Theorem)

재귀 트리(Recursion Tree Theorem)란?

각 노드가 재귀호출되는 하위 문제에 대한 비용을 나타내는 방법입니다.

치환법으로 추측이 불가능할 때 사용합니다.

 

 

Step 1: 식 구하기 

---

T(n) = 3T(n/4) + Θ(n2)

 

계수는 중요하지 않으므로 Θ를 풀 때 c(c>0)로 대체해줍니다.

 

T(n) = 3T(n/4) + cn²

 

 

 

Step2: 재귀트리 구하기

---

cn²을 기준으로 3개의 branch를 생성해줍니다.

 

  

위와 같은 방식으로 계속 branch를 생성해 줍니다.

 

 

T(1)이 나올 때까지 트리를 이어가 줍니다.

 

 

 

Step3: 트리의 길이(height) 구하기

---

그림을 따라서 각각의 트리 레벨의 길이를 구하다보면 트리의 총 길이는 1 = n/4ʰ임을 알 수 있습니다.

1 = n/4ʰ 은 n = 4ʰ로 바뀌고, log 공식을 통해 h = Log₄n가 됩니다.

 

 

Step4:  각 레벨의 항의 개수 구하기

---

각 레벨의 항의 개수를 보면 3의 배수만큼 증가하는 것을 확인할 수 있습니다.

마지막을 레벨을 보면 항의 개수는 3ʰ이고 위에서 구했던 트리의 길이를 사용하여 계산을 더 이어가 줍니다.

3ʰ = 3ˡºᵍ⁴ⁿ이고, 밑과 로그 공식을 하면 nˡºᵍ⁴³ 을 구할 수 있습니다.

(3ˡºᵍ⁴ⁿ 4는 밑 n은 지수, nˡºᵍ⁴³ 4는 밑, 3은 지수입니다.)

 

 

 

 

Step5:  total 합 구하기

---

각각의 길이와 항의 개수를 곱해서 식을 구해주고,

 

 

시그마 공식을 이용해서 결과를 구해주면 됩니다.

마지막 결과를 통해 time complexity는 θ(n²)라는 것을 알 수 있습니다.

 

 

 

◡̈