Подстановка решения в рекуррентное отношение сортировки слиянием

Аргументы, которые позволили прийти к выводу (5.2), могут использоваться для определения того, что функция T(n) ограничивается O(n log n). С другой стороны, если у вас имеется гипотеза относительно времени выполнения, ее можно прове- рить, подставив ее в рекуррентное отношение.

Допустим, вы предполагаете, что T(n) < cn log2 n для всех n > 2, и хотите проверить, так ли это. Для n = 2 оценка очевидно верна, так как в этом случае cn log2 n = 2c, а в (5.1) явно указано, что Г(2) < с. Теперь предположим по индукции, что Г(m) < cm log2 m для всех значений m, меньших n; теперь нужно доказать, что гипотеза выполняется для T(n). Для этого запишем рекуррентное отношение для T(n) и подставим его в неравенство Г(n/2) < c(n/2) log2(n/2). Полученное выраже- ние можно упростить, если заметить, что log2(n/2) = (log2 n) - 1. Ниже приведены полные вычисления.

Искомая граница для T(n) доказана в предположении, что она действительна для меньших значений m < n; рассуждение по индукции завершено.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Подстановка решения в рекуррентное отношение сортировки слиянием:

  1. Слияние с Гуру
  2. 5) Слияние с Мастером
  3. Статья 106. Слияние, присоединение, деление и преобразование юридического лица
  4. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  5. Статья 107. Порядок прекращения юридического лица путем слияния, присоединение, деления и преобразования
  6. Сефера: Крайон, для чего все эти существа прибыли вместе с нами из Атлантиды? Для чего слияние рас прошлого и настоящего (или будущего)?
  7. § 1 Общие свойства семейственных отношений. – Общественный их характер. – В чем они подчиняются юридическому определению. – Свойство семейной власти и отличие ее от обладания. – Вопросы и иски о состоянии, соединенные с семейными правами. – Восстановление семейной власти. – Вмешательство правительственной власти в семейные отношения. – Отношения родственные.
  8. Статья 9. Применение Гражданского кодекса Украины к урегулированию отношений в сферах хозяйствования, использование естественных ресурсов, охраны окружающей среды, а также к трудовым и семейным отношениям
  9. РЕШЕНИЕ
  10. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  11. з) Совершение преступления в отношении женщины, заведомо для виновного находящейся в состоянии беременности, а также в отношении малолетнего, другого беззащитного или беспомощного лица, либо лица, находящегося в зависимости от виновного
  12. Решение проблем
  13. ПРИНЯТИЕ РЕШЕНИЙ
  14. § 45 Договор о найме имуществ. – Предмет его. – Плата. – Отношение сторон. – Обязанность хозяина. – Передача. – Поддержание имущества. – Обязанности наемщика и права его. – Сублокация. – Эмфитевтическое пользование и бессрочный наем. – Право отказа. – Значение владения в найме и отношение его к праву собственности. – Действие давности. – Возобновление найма. – Ограждение наемщика и хозяина особым процессом. – Отношение найма к узуфрукту. – Наем земельный. – Правила арендных договоров. – Наем изп
  15. РЕШЕНИЯ КСУ
  16. Не избегайте принятия решений
  17. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  18. Взаимоотношения и сексуальность в Телосе Адама, расскажи, пожалуйста, об отношениях между мужчинами и женщинами в Телосе. Как относятся к сексуальности в вашем городе? Как люди в третьем измерении могут эволюционировать до такого уровня отношений?
  19. ЗАДАЧА: РЕШЕНИЕ