|
Проверить, выполняются ли условия Основной теоремы о рекуррентных оценках (см. Кормен Алгоритмы. Построение и анализ, глава 4) и получить оценку для алгоритма, который разбивает задачу размера $%n$% на 4 подзадачи размера $%\frac{n}{2}$% и использует для этого $%\theta(\frac{n^2\sqrt{n}}{log^2{n}})$% операций. задан 29 Фев '16 1:25 
Uchenitsa |
|
Если я правильно понимаю постановку задачи, то здесь рассматривается функция $%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 @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
|