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

Этот более общий класс алгоритмов образуется при рассмотрении алгоритмов «разделяй и властвуй», которые создают рекурсивные вызовы для 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.