@exgod
Трудно быть Богом.

Каким способом решить рекуррентное уравнение?

Как решить рекуррентное уравнение вида:
T( n) =4T(2n/3) + 1, T(1) = 3?

Рассматривал один пример:
T(n) = 2T(n/2) + 5n2
T(1) = 7


Решение:
Для простоты мы предположим, что n является степенью 2 , т.е. n = 2к
T(n) = 2T(n/2) + 5n2 =
= 2(2T (n/4) + 5 (n/2)2 ) + 5n2 =
= 2(2(2T (n/8) + 5 (n/4)2 ) + 5 (n/2)2 ) + 5n2 =…=
=2к T(1) + 2к-1 · 5 (n/2k-1 ) 2 + … + 2 · 5 (n/2)2 + 5n2


но так и не могу въехать, что и откуда берётся.

Какими источниками для ознакомления можно воспользоваться?
Что-то искал в книге Вилинкина (Комбинаторика), но успех обошёл меня стороной.
  • Вопрос задан
  • 123 просмотра
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
CSort Барнаул
от 40 000 до 90 000 руб.
Chudo Москва
от 80 000 до 140 000 руб.
SegmentStream Москва
от 250 000 до 350 000 руб.
21 июл. 2019, в 00:52
80000 руб./за проект
20 июл. 2019, в 19:38
10000 руб./за проект
20 июл. 2019, в 17:55
15000 руб./за проект