반복 방법을 사용하여 재발 관계 해결

Question

이 예를 고려하십시오 :

T(n) = T(7n/8) + 2n 

나는 t (1) = 0이라고 가정했다

다음과 같이 해결하려고했습니다

T(n) = T(7n/8) + 2n
     = T(49n/64) + 2.(7n/8) + 2n
     = T(343n/512) + 2.(7n/8).(7n/8)+ 2.(7n/8) + 2n 
     = T(1) + 2n ( (7n/8)^i + ..... + 1)               

그러나 나는 이것에 대한 결론에 도달 할 수 없었다. 다음 단계에서 무엇을 해야하는지 혼란스러워합니다.

Answer 1

접근 방식은 건전하지만 약간 다르게 다시 작성하면 어떻게 해야하는지 알 수 있습니다.

T(n) = T((7/8)^1 * n) + 2 * (7/8)^0 * n
     = T((7/8)^2 * n) + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n
     = T((7/8)^3 * n) + 2 * (7/8)^2 * n + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n
     .
     .
     .
     = T((7/8)^k * n) + 2 * n * sum j = 0 to k-1 (7/8)^j

자,하자 k 무한대를 보이고 무슨 일이 일어나는지 보는 경향이 있습니다. 친숙하다면 도움이 될 것입니다 기하학적 시리즈.

Answer 2

t (n) = t (7n/8) + 2n = 2n * (1 + 7/8 + (7/8)^2 + ... (7/8)^z) + t (1) 여기서 z = ?

유일한 속임수는 Z를 찾는 것입니다. 로그가 도움이 될 것입니다. 죄송합니다. 늦었고 똑바로 생각하지는 않지만 여러분 2N을 추가 할 필요는 없습니다.

편집 : z는 1을 얻을 때까지 n을 7/8로 곱할 시간이 얼마나 많은지입니다.

그래서, n * 7^z / 8^z = 1

(7/8)^z = 1/n

(8/7)^z = n

당신은 Z를 위해 해결하고 싶습니다.

Answer 3

마지막 줄에서 거기에 도착한 것은 기하학적 시리즈 그리고 A가 있습니다 공식 그러한 합계를 단순화합니다.