Похожее рекуррентное отношение: T(n) < 2T(n/2) + O(n2)

В завершение темы рассмотрим последнее рекуррентное отношение; оно поучи- тельно и как пример убывающей геометрической суммы, и как интересный кон- траст с рекуррентным отношением (5.1), которым характеризовалась сортировка слиянием.
Более того, его разновидность будет рассматриваться в главе 6, когда мы займемся анализом алгоритма «разделяй и властвуй» для решения задачи вы- равнивания последовательностей с малыми затратами памяти.

Рекуррентное отношение базируется на следующей структуре «разделяй и вла- ствуй»: входные данные разбиваются на два блока равного размера; две подзадачи для этих блоков рекурсивно решаются по отдельности; два результата объединя-
ются в одно решение, с квадратичными затратами времени для исходного деления и итогового объединения.

Для наших целей важно то, что алгоритмы такого рода имеют время выполнения T(n), удовлетворяющее следующему рекуррентному отношению:

(5.6) Для некоторой константы c

Инстинктивно хочется предположить, что решение будет иметь вид T(n) = O(n2 log n), поскольку оно почти идентично (5.1), если не считать увеличения объема работы на уровень с коэффициентом, равным размеру входных данных. На самом деле эта верхняя граница верна (хотя для обоснования потребуются более содержательные обоснования, чем предыдущее предложение), но также выясня- ется, что верхнюю границу можно усилить. Для этого мы выполним раскрутку рекуррентности по стандартному шаблону.

♦ Анализ нескольких начальных уровней: на первом уровне рекурсии имеется одна задача с размером n, которая выполняется за время cn2 плюс время, потраченное на все последующие рекурсивные вызовы. На следующем уровне имеются две задачи с размером n/2.

Каждая из них вносит вклад (cn/2)2 = cn2/4, что в сумме дает максимум cn2/2, и снова плюс время, потраченное на последующие рекур- сивные вызовы. На третьем уровне имеются четыре задачи, каждая из которых имеет размер n/4 и занимает время максимум c(n/4)2 = cn2/16, в сумме не более cn2/4. Уже видно, что ситуация отличается от решения для аналогичного ре- куррентного отношения (5.1); тогда общий объем работы на уровень оставался неизменным, а здесь он сокращается.

Выявление закономерности: на произвольном уровне j находятся 2 подзадач, каждая из которых имеет размер п/2Л Следовательно, общий объем работы на

этом уровне ограничиваете


♦ Суммирование по всем уровням рекурсии: после всех вычислений мы пришли почти к такой же сумме, которая использовалась для случая q = 1. Получаем

Второе неравенство следует из того факта, что мы имеем дело со сходящейся геометрической суммой.

Оглядываясь назад, видим, что наше исходное предположение T(n) = O(n2 log n),

базирующееся на аналогии с (5.1), было завышенным из-за скорости убыва-

∕ \2 ∕ \2 ∕ \2

ния составляющей n2 при замене ее

рекуррентного отношения. Из-за этого мы получаем геометрическую сумму вместо суммы, растущей на фиксированную величину по всем n уровням (как в реше- нии (5.1)).

5.3.

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

Еще по теме Похожее рекуррентное отношение: T(n) < 2T(n/2) + O(n2):

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