Решить уравнение: $%T(n)=nT(\tfrac{n}{2})+O(n)$%

задан 17 Фев '18 3:25

изменен 17 Фев '18 3:25

1

Здесь всё довольно просто получается напрямую: без добавочного члена O(n) при n=2^k получится T(n)=2^{k}2^{k-1}...2^{1}=2^{k(k+1)/2}. Далее рассматривается общий случай 2^k <= n < 2^{k+1}. Наличие члена O(n) чуть увеличивает эти оценки, но не слишком существенно. Остальное -- дело техники.

(18 Фев '18 0:02) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×211
×59
×55

задан
17 Фев '18 3:25

показан
186 раз

обновлен
18 Фев '18 0:02

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru