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

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

В последней строке вы получили геометрический ряд , а для упрощения такой суммы есть формула .

Answer 3

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.