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

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

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

Случай q > 2 встретится позднее в этой главе, когда мы займемся разработкой алгоритмов для целочисленного умножения; разновидность с q = 1 будет представлена позднее, когда мы будем разрабатывать рандомизированный алгоритм нахождения медианы в главе 13.

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

(5.3) Для некоторой константы c, для n>2, и T(n) ≤ qT(n/2) + cn T(2) ≤ c

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