되풀이 관계 : T (n) = 2T (n/4) + T (n/2) + n^2

Question

저는 이러한 반복 관계에 대해 연구하고 있습니다.

T(n) = 2T(n/4) + T(n/2) + n^2 

나는 하나의 재귀 호출하지만 두에로 봤어요.

Answer 1

이러한 종류의 재발은 Akra-Bazzi method으로 해결됩니다.

귀하의 경우에는 a1 = 2, a2 = 1, b1 = 1/4, b2 = 1/2입니다. 따라서 방정식을 풀어야합니다 :

2/4^p + 1/2^p = 1 

해결 방법은 p=1입니다. 이제 g(x) = n^2이 있기 때문에 1에서 x까지의 정수는 x - 1이됩니다. 따라서 복잡성은 단지 x^p(1 + x - 1) = O(x^2)