Проверить, выполняются ли условия Основной теоремы о рекуррентных оценках (см. Кормен Алгоритмы. Построение и анализ, глава 4) и получить оценку для алгоритма, который разбивает задачу размера $%n$% на 4 подзадачи размера $%\frac{n}{2}$% и использует для этого $%\theta(\frac{n^2\sqrt{n}}{log^2{n}})$% операций.
Насколько я понимаю, под условие теоремы задача не подходит. Подскажите, пожалуйста, какую оценку подобрать.

задан 29 Фев '16 1:25

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

Если я правильно понимаю постановку задачи, то здесь рассматривается функция $%T(n)=4T(\frac{n}2)+f(n)$%, где $%f(n)=O(\frac{n^{5/2}}{\log^2n})$%. Ясно, что для "чистого" равенства $%T(n)=4T(\frac{n}2)$% получается $%n^2$%, а у добавочного члена показатель степени больше, поэтому именно он и влияет на рост. Тогда для $%T(n)$% получается оценка того же порядка. Это доказывается по индукции для некоторой достаточно большой константы $%C$%. А именно, если $%f(n)\le C_1\frac{n^{5/2}}{\log^2n}$%, то для первого слагаемого по индукции мы имеем оценку $%4T(\frac{n}2)\le C\frac{n^{5/2}}{\sqrt2\log^2(n/2)}\le\frac34C\frac{n^{5/2}}{\log^2n}$% за счёт того, что отношение $%\frac{\log n}{\log(n/2)}=\frac{\log n}{\log n-1}$% стремится к единице, и при достаточно больших $%n$% его можно оценить сверху любой константой, превышающей единицу. С этой целью мы увеличили множитель $%\frac1{\sqrt2}$% до $%\frac34$%.

После сложения получается константа $%\frac34C+C_1\le C$%, если взять $%C\ge4C_1$%. Для того, чтобы неравенства были верны для конечного набора начальных значений $%n$%, её можно соответствующим образом увеличить.

ссылка

отвечен 29 Фев '16 2:37

@falcao, спасибо за ответ! Получается, что мы оцениваем задачу как $%O(\frac{n^{5/2}}{log{n}^2})$%. Но в условии было $%f(n)=\theta(\frac{n^{5/2}}{log{n}^2})$%. Может здесь нужно еще оценку снизу рассмотреть?

(29 Фев '16 13:05) Uchenitsa

@Uchenitsa: я этот момент не рассматривал, так как оценка снизу нам дана. Ясно, что T(n) не меньше f(n), а f(n) не меньше C'*n^{5/2}/(log n)^2 по условию. То есть я это опустил в силу очевидности.

(29 Фев '16 14:08) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×154
×72
×48

задан
29 Фев '16 1:25

показан
533 раза

обновлен
29 Фев '16 14:08

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

по почте:

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

по RSS:

Ответы

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

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