Решение рекуррентного соотношения с использованием итерационного метода

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 - это сколько раз вам нужно умножить n на 7/8, пока не получится 1.

Итак, n * 7 ^ Z / 8^Z = 1

(7/8)^Z = 1/n

(8/7)^Z = n

Вы хотите решить для Z.

Answer 3

То, что у вас есть там, в последней строке, - это геометрический ряд и есть такой формула чтобы упростить такую сумму.