재귀 트리를 사용하여이 재귀 문제를 해결하고 있습니다. 각 레벨의 총 비용은 n이고 트리의 깊이는 log (n) base 4과 log (n) base 4/3 사이입니다. 직관적으로, 나는 솔루션이 최대 레벨 수와 각 레벨의 비용을 곱하기를 기대합니다. O(cn log (n) base 4/3) = O(n log n). 나는 문제에 대한 나의 접근 방식과 나의 해결책이 맞는지 궁금했다.재귀 복잡성을 풀는 방법 T (n/4) + T (3n/4) + cn
첫 번째 로그의 경우 재귀 트리의 n 번째 레이어 4 개 모두 해당 하위 트리의 전체 크기를 합산하면 총계가 cn이므로 총계가 n이어야합니다. 이것은 수행 된 작업이 Ω (n log n)임을 의미합니다.
트리의 각 레이어에서 수행 된 작업의 합계가 O (n) 인 것으로 가장하여 작업을 상위 바인딩 할 수 있습니다 (트리에서 아래로 갈수록 실제로 떨어집니다. 상한)이고 높이는 로그 4/3 n입니다. 이것은 O (n log n)의 작업에 대한 상한을 제공합니다.
작업이 Ω (n log n)이고 O (n log n)이므로 작업이 더 올바르게 수행됩니다. Θ (n log n).
희망이 도움이됩니다.
편집이 : 아래의 영업 이익을 누락 잘못된 솔루션을 대답되었습니다 것은 직관적으로 내 정제 시도
, 당신 말이 맞아.
보다 공식적인 접근법을 위해 수학적으로 증명할 수 있습니다.
마술 트릭은 여기에 있습니다 : 우리는 정리하여 g(n) = cn, k = 2, a1 = a2 = 1, b1 = 1/4, b2 = 3/4
있어 T(n) = T(n/4) + T(3n/4) + cn
의 관계를 들어 마스터 정리
의보다 일반적인 버전입니다 Akra-Bazzi theorem, 우리는 a1b1^p + a2b2^p = 1에 대한 페이지를 해결해야 이것은 분명히 p = 1이다.
우리의 추측과 일치