목록Recursion tree theorem (1)

YYYEJI

[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ʰ로 ..
Algorithm 2023. 4. 16. 19:07
이전 Prev 1 Next 다음