Другие рекуррентные отношения
Этот более общий класс алгоритмов образуется при рассмотрении алгоритмов «разделяй и властвуй», которые создают рекурсивные вызовы для 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.
Еще по теме Другие рекуррентные отношения:
- § 1 Общие свойства семейственных отношений. – Общественный их характер. – В чем они подчиняются юридическому определению. – Свойство семейной власти и отличие ее от обладания. – Вопросы и иски о состоянии, соединенные с семейными правами. – Восстановление семейной власти. – Вмешательство правительственной власти в семейные отношения. – Отношения родственные.
- Статья 9. Применение Гражданского кодекса Украины к урегулированию отношений в сферах хозяйствования, использование естественных ресурсов, охраны окружающей среды, а также к трудовым и семейным отношениям
- «Я» и другие
- § 6. Другие некоммерческие организации
- 3.10. Другие упражнения
- Другие соображения
- Другие упражнения.
- § 10. Другие способы обеспечения
- Другие важные прогрессии
- § 3. Земля и другие природные ресурсы
- Другие полномочия правительства
- 5.2.4. Другие следы человека
- Другие наши способности
- То, что вы подавляетЕ, выразят другие