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

Рассмотрим следующий пример:Решая рекуррентное соотношение, используя итерационный метод

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)

, но Я не мог прийти к какому-либо заключению об этом. Я смущен тем, что я должен сделать на следующем шаге.

источник

2010-01-13 Tasbeer

Ваш подход звук, но вы увидите, что делать, если вы переписать несколько иначе:

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 стремятся к бесконечности, и посмотрим, что произойдет. Это поможет, если вы знакомы с geometric series.

источник

2010-01-13 00:30:59 jason

Если я возьму k -> бесконечность, то в правой части я получу 8 как S (inf) = a/1-r = 1/(1 -7/8) = 8 , что приводит к порядку O (n). Снова я не уверен, правильно ли это :( – Tasbeer

Это точно! Сумма равна 8. Теперь что происходит с '(7/8)^k' как' k' стремится к бесконечности? – jason

mmm, что было бы бесконечно – Tasbeer

T (n) = T (7n/8) + 2n = 2n * (1 + 7/8 + (7/8)^2 + ... (7/8)^Z) + T (1), где Z =?

Единственный трюк - найти Z. Я ставлю, что журнал поможет. Извините, что уже поздно, и я не думаю прямо, но ... вам не нужно добавлять несколько 2n.

Edit: Z, сколько времени вам нужно умножить п на 7/8, пока вы не получите 1.

Так, п * 7^Z/8^Z = 1

(7/8)^Z = 1/п

(8/7)^Z = п

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

источник

2010-01-13 00:22:26

Я пытался делать это (7/8)^Z = 1/п и взял журнал, как вы сказали, база которого 7/8, который дал мне Z = логарифм по основанию 7/8 (1/п) и замещенный это в формуле суммирования геометрических рядов: T (n) = 2n * 8 (1- (1/n)) , который дает O (n^2) ... не уверен, что это правильно. – Tasbeer

Logartihms не требуется для решения этой проблемы; Я не могу придумать подход, в котором они, естественно, приходят. – jason

Как сказал другой плакат: ust пусть он бежит до бесконечности ... –

то, что вы получили там в последней строке является geometric series и есть formula - упростить такую сумму.

источник

2010-01-13 00:26:45 sth

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

ответ

Смежные вопросы