Пытался делать предположения: $%T(n) \le cn \lg \frac n2$%, $%T(n) \le cn \lg (n + d)$%, $%T(n) \le cn \lg(n - d)$%, $%T(n) \le cn \lg 2n$%, $%T(n) \le cn \lg n + d$%.
Но никакое из них не приводит к результату.

alt text

alt text

задан 7 Июл '15 19:37

изменен 7 Июл '15 20:29

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

А в чём именно состоит задание? Что нужно доказать?

Вообще, здесь при любом начальном значении $%T(1)$% можно по индукции получить равенство для степеней двойки, а затем заключить $%n$% между соседними степенями двойки. Этого обычно хватает.

(7 Июл '15 20:55) falcao

Нужно доказать, что $%T(n) = O(n \lg(n))$%.

(7 Июл '15 22:21) Leva319

@Leva319: так ведь это уже в предыдущих задачах было. Здесь разницы нет почти никакой. Пусть $%T(1)=c$%, тогда $%T(2)=2c+2$%, $%T(4)=4c+8$%, ... , и по индукции $%T(2^k)=2^kc+k2^k=2^k(k+c)$%. Тогда при $%2^k\le n < 2^{k+1}$% получается $%T(n)\le T(2^{k+1})=2^{k+1}(k+c+1)\le2n(\log n+c+1) < 4n\log n=O(n\log n)$% при $%n\gg1$%.

(7 Июл '15 22:44) falcao

Получается, что мы доказали рекуррентное соотношение для степеней двойки и для таких n что lgn > c + 1 (другими словами, для достаточно больших n). Но это же не значит, что соотношение верно для ВСЕХ n?

(11 Июл '15 20:41) Leva319

@Leva319: перечитайте определение "O-большого". Это асимптотическая характеристика. Она не зависит от конечного числа начальных значений -- как и сходимость рядов. Дело в том, что если отношение f(n)/g(n) не превосходит C для n>>1, то для конечного числа значений можно взять максимум, который тоже равен какой-то константе. Поэтому итоговое значение константы всегда можно увеличить до такого, чтобы ограничение имело место для всех n.

(11 Июл '15 20:46) falcao
10|600 символов нужно символов осталось
0

$$\eqalign{ & T(n) = 2T(n/2) + n \Leftrightarrow T(n/2) = 2T(n/4) + n/2 \cr & T(n) = 4T(n/4) + 2n \Leftrightarrow T(n/4) = 2T(n/8) + n/4 \cr & T(n) = 8T(n/8) + 3n \Leftrightarrow T(n/8) = 2T(n/16) + n/8 \cr & \cdots \cr & T(n) = {2^k}T(n/{2^k}) + kn;\,\,\,T(1) = 1 \Leftrightarrow k = {\log _2}n \cr & T(n) = n + n{\log _2}n \in O(n\log n) \cr} $$

ссылка

отвечен 8 Июл '15 3:10

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

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

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

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

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

отмечен:

×63
×21

задан
7 Июл '15 19:37

показан
631 раз

обновлен
11 Июл '15 20:46

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

по почте:

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

по RSS:

Ответы

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

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