Другие рекуррентные отношения

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

Этот более общий класс алгоритмов образуется при рассмотрении алгоритмов «разделяй и властвуй», которые создают рекурсивные вызовы для q подзадач с размером n/2 каждая, а затем объединяют результаты за время O(n). Это соответ- ствует рекуррентному отношению сортировки слиянием (5.1) с q = 2 рекурсивных вызовов, или всего одним (q = 1) рекурсивным вызовом. Случай q > 2 встретится позднее в этой главе, когда мы займемся разработкой алгоритмов для целочислен- ного умножения; разновидность с q = 1 будет представлена позднее, когда мы бу- дем разрабатывать рандомизированный алгоритм нахождения медианы в главе 13.

Если T(n) обозначает время выполнения алгоритма, построенного по такому принципу, то T(n) подчиняется следующему рекуррентному отношению, которое напрямую обобщает (5.1) с заменой 2 на q:

(5.3) Для некоторой константы с,

В следующем разделе описано, как решить (5.3) с использованием уже при- менявшихся методов: раскрутки, подстановки и частичной подстановки. Случаи q > 2 и q = 1 рассматриваются по отдельности, так как они качественно отличаются друг от друга, а также от случая q = 2.

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

Еще по теме Другие рекуррентные отношения:

  1. § 1 Общие свойства семейственных отношений. – Общественный их характер. – В чем они подчиняются юридическому определению. – Свойство семейной власти и отличие ее от обладания. – Вопросы и иски о состоянии, соединенные с семейными правами. – Восстановление семейной власти. – Вмешательство правительственной власти в семейные отношения. – Отношения родственные.
  2. Статья 9. Применение Гражданского кодекса Украины к урегулированию отношений в сферах хозяйствования, использование естественных ресурсов, охраны окружающей среды, а также к трудовым и семейным отношениям
  3. «Я» и другие
  4. § 6. Другие некоммерческие организации
  5. 3.10. Другие упражнения
  6. Другие соображения
  7. Другие упражнения.
  8. § 10. Другие способы обеспечения
  9. Другие важные прогрессии
  10. § 3. Земля и другие природные ресурсы
  11. Другие полномочия правительства
  12. 5.2.4. Другие следы человека
  13. Другие наши способности
  14. То, что вы подавляетЕ, выразят другие