Решение рекуррентных соотношений

Мультипликативные функции. Частное решение в формуле (9.16) оценить достаточно трудно, даже если известен вид функции d(n). Но для определенного, достаточно широкого класса функций d(n) можно найти точное решение (9.16). Будем говорить, что функция f целочисленного аргумента называется мультипликативной, если для всех положительных целых чисел х и у справедливо равенство f(xy) = f(x)f(y).
Пример 9.2. Для нас наибольший интерес представляют мультипликативные функции вида , где — некоторая положительная константа. Чтобы показать, что функция f(n)= является мультипликативной, достаточно заметить, что
Пусть в (9.16) функция d(n) является мультипликативной, тогда. В этом случае частное решение запишется в следующем виде:
(9.17)
Теперь необходимо рассмотреть три ситуации, зависящие от того, будет ли параметр а больше, меньше или равен d(b).
1. Если а>d(b), тогда последнее выражение в (9.17) имеет порядок О(а^k), который можно переписать как n^logka , поскольку k=log_bn. В этом случае частное и однородные решения имеют одинаковый порядок роста, который зависит только от а и b, но не от управляющей функции. Поэтому в данной ситуации уменьшение времени выполнения алгоритма можно достичь путем уменьшения а или увеличения b, уменьшение порядка роста функции d(n) здесь не поможет.
2. Если аk). В этом случае частное решение превышает однородное. Поэтому для уменьшения времени выполнения алгоритма можно манипулировать как функцией d(n), так и параметрами а и b. В важном частном случае, когда , d(b) будет равно и. Тогда частное решение имеет порядок или O(d(n)).
3. Если а=d(b), тогда надо пересмотреть решение (9.17), поскольку в данном случае нельзя применять формулу суммирования членов геометрической прогрессии. В этой ситуации суммируем следующим образом:
(9.18)
Поскольку а=d(b), то частное решение (9.18) равно однородному решению, умноженному на log_bn. Здесь опять частное решение превосходит однородное. В частном случае, когда , решение (9.18) имеет порядок .
Пример 9.3. Рассмотрим следующие рекуррентные уравнения с начальным значением T(1) = 1.
1. Т(n) = 4T(n/2)+ n.
2. Т(n) = 4T(n/2) + n².
3. Т(n) = 4T(n/2) + n³.
В каждом уравнении а=4 и b=2, следовательно, однородное решение равно n². В уравнении (1) d(n)=n, поэтому d(b)=2. Поскольку а=4>d(b), то частное решение также имеет порядок n². Поэтому здесь Т(n) = О(n²).
В уравнении (3) d(n)=n², d(b)=8 и а3).
В уравнении (2) d(b)=4=а, поэтому решение дается формулой (9.18). Здесь как частное решение, так и Т(n) имеют порядок О(n² logn).


Другие управляющие функции. Существуют другие типы управляющих функций, отличные от мультипликативных, которые позволяют получить замкнутую форму решения (9.16). Мы рассмотрим только два примера таких функций. В первом примере получаем небольшое обобщение мультипликативных функций, а именно, здесь рассматриваются мультипликативные функции, умноженные на константу, которая больше или равна единице. Во втором примере просто показан частный случай функции d(n), позволяющий получить замкнутую форму решения (9.16).
Пример 9.4. Рассмотрим следующее рекуррентное уравнение:
Т(1) = 1,
T(n) = 3T(n/2) + 2n^1,5.
Выражение 2n^1,5 не является мультипликативной функцией, но функция n^1,5 является. Сделаем замену U(n)=T(n)/2 для всех n. Тогда исходное рекуррентное перепишется в виде
U(1) = 1/2,
U(n) = 3U(n/2) + n^1,5.
Если бы U(1) равнялось 1, тогда однородное решение равнялось бы n^log3< n^1,59. Для U(1) = 1/2 можно показать, что однородное решение не больше n^1,59/2, т.е. имеет порядок О(n^1,59). На частное решение значение U(l) не влияет. Поскольку в данном случае а=3, b=2 и b^1,5=2.83<а, то частное решение, а также и U(n) имеют порядок роста О(n^1,59). Так как T(n) = 2U(n), то Т(n) тоже имеет порядок О(n^1,59), точнее O(n^log3).
Пример 9.5. Рассмотрим рекуррентное уравнение
T(1)=1,
Т(n) = 2T(n/2) + nlogn.
Легко проверить, что в данном случае однородное решение равно n, поскольку а=b=2. Но функция d(n)=nlogn мультипликативной не является, поэтому надо попытаться найти значение суммы в формуле (9.16). В данном случае имеем
.
Так как k=logn, то частное решение имеет порядок О(nlog²n). Поскольку здесь частное решение больше однородного, то отсюда следует, что Т(n) также будет иметь порядок О(nlog²n).


Контрольные вопросы

1.Когда говорят эффективность алгоритмов, что Вы понимаете.

2. Анализ рекурсивных программ
3. Решение рекуррентных соотношений