어떻게 재발을 펼칠 수 있습니까? T (n) = 2T ((n + 2)/3)

Question

이 재발 문제를 해결하려고하지만이를 펼칠 방법을 모르겠습니다.

T(n)=2T((n+2)/3) + 1 

"+2"를 무시하고 2T (n/3) + 1로 해결할 수 있습니까?

이이 수익을 V[a..b] 배열을 사용하고 있습니다 문제에서에서 온다 :의 ((b-a+3)/3) = ((n+2)/3)

Answer 1

정렬 : Y 그래서 (2a+b)/3 and Z is (a+2b)/3

입니다

return V(X) + f(V, a, Y) + f(V, Z, b) 

. 이 트릭의 엄격한 버전 U(n) = T(n+1)을 설정하고

U(n) = T(n+1) 
    = 2T((n+1+2)/3) + 1 
    = 2T(n/3 + 1) + 1 
    = 2U(n/3) + 1. 

그런 다음 U에 대한 해결 작성하는 것입니다 (예를 들어, U(n) = O(n^log3(2))) 한 다음 동일한 순서의 T에 대한 점근 적 표현을 찾을 수 있어야합니다.