Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
17 Фев '18 3:25
показан
224 раза
обновлен
18 Фев '18 0:02
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Здесь всё довольно просто получается напрямую: без добавочного члена 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) чуть увеличивает эти оценки, но не слишком существенно. Остальное -- дело техники.