а) T(n)= 2T(n/3) + nlogn
b) T(n) = T(n/5) + T(4n/5) + Theta(n)
c) T(n) = sqrt(n)T(sqrt(n)) + 100n

Комментарии:

1) f(n) = Theta(g(n)) <=>

Существуют такие a,b>0 и такое m, что 0<=ag(n)<=f(n)<=bg(n) для всех n>=m.

2) В пункте a), возможно, следует использовать основную теорему о рекуррентных соотношениях, но трудно определить и доказать, к какому пункту она подходит.

задан 16 Фев '16 20:10

изменен 16 Фев '16 20:10

10|600 символов нужно символов осталось
0

a) http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%81%D1%82%D0%B5%D1%80-%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0

собс-но, нафига Вам эта "основная" теорема: итерируйте соотношение в a) и будет Вам счастье

b) здесь ясно, что $%T(n)$% растет быстрее, чем $%Cn$%, но медленнее, чем $%Cn^{1+\epsilon}$%. Можно разделить на $%n$% и сделать очевидную подстановку. Далее через тривиальную оценку видно, что новая искомоя функция растет не быстрее, чем логарифм и не медленнее, чем логарифм. Делаем подстановку вида $%\sim C\ln n$%, находим константу, вуаля.

c) разделите на $%n$% и сделайте подстановку, дальше очевидно

ссылка

отвечен 16 Фев '16 21:06

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×154
×63
×48

задан
16 Фев '16 20:10

показан
520 раз

обновлен
16 Фев '16 21:06

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

по почте:

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

по RSS:

Ответы

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

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