@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


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

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

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

Войти через центр авторизации
Похожие вопросы