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

Решение рекуррентных соотношений. Существуют три различных подхода к решению рекуррентных соотношений.
1. Нахождение функции f(n), которая мажорировала бы Т(n) для всех значений n (т.е. для всех n>1 должно выполняться неравенство Т(n)≤ f(n)). Иногда сначала мы будем определять только вид функции f(n), предполагая, что она зависит от некоторых пока неопределенных параметров (например, f(n)=an², где а —неопределенный параметр), затем подбираются такие значения параметров, чтобы для всех значений n выполнялось неравенство Т(n)≤f(n).
2. В рекуррентном соотношении в правую часть последовательно подставляются выражения для T(m), m1, оставляя только T(1). Поскольку T(1) всегда является константой, то в результате получим формулу для Т(n), содержащую только n и константы. Такая формула и называется "замкнутой формой" для Т(n).
3. Третий подход заключается в использовании общих решений определенных рекуррентных соотношений, приведенных в этой главе или взятых из других источников (см. библиографические примечания).
Общее решение большого класса рекуррентных уравнений. Рассмотрим решение рекуррентных соотношений, когда исходную задачу размера n можно разделить на а подзадач каждую размера n/b. Для определенности будем считать, что выполнение задачи размера 1 требует одну единицу времени и что время "сборки" подзадач, составляющих исходную задачу размера n, требует d(n) единиц времени. В примере процедуры mergesort а=b=2 и d(n)=c₂n/c₁ в единицах c₁. Тогда, если обозначить через Т(n) время выполнения задачи размера n, будем иметь
T(1)=1,
T(n)=aT(n/b)+d(n) (9.14)
Отметим, что соотношение (9.14) можно применить только тогда, когда n является целой степенью числа b. Но если функция Т(n) достаточно гладкая, то решение, полученное в предположении, что n является целой степенью числа b, можно будет распространить на другие значения n.
Заметим также, что в (9.14) мы имеем уравнение, тогда как в (9.1) имели неравенство. Причина заключается в том, что в (9.14) используется пока произвольная функция d(n), поэтому мы имеем право записать точное равенство. А в (9.1) выражение с₂n соответствует времени выполнения операции слияния списков в самом худшем случае и поэтому является верхней оценкой; фактическое время выполнения процедуры mergesort на входных данных размера n может быть меньше 2Т(n/2)+с₂n. С другой стороны, не имеет значения, используем ли мы в рекуррентных соотношениях знак равенства или знак неравенства, поскольку мы ищем только верхнюю границу времени выполнения в самом худшем случае.
Для решения уравнения (9.14) применим метод подстановки, рассмотренный в предыдущем разделе. Итак, подставим в (9.14) вместо n выражение n/bⁱ:

Подставляя в (9.14) равенства (9.15) последовательно для i=1, 2,… получим

Если, как мы предположили, n=b^k, тогда при i=k Т(n/b^к)=Т(1)=1 и мы получаем формулу

(9.16)
Так как k=log_bn, то первое выражение в (9.16) можно записать как a^log_bⁿ или, что эквивалентно, как n^log_b^a. Таким образом, это выражение обозначает n в степени, которая зависит от а и b. Например, в случае процедуры mergesort а=b=2, поэтому первое выражение равно просто n. В общем случае, чем больше а (т.е. надо решить большее количество подзадач), тем больший показатель степени n. При больших значениях b (чем больше b, тем меньше размер подзадач) показатель степени n будет меньше.
Однородные и частные решения. Интересно исследовать, какова роль обоих выражений в формуле (9.16). Первое выражение а^k или n^log_b^a называется однородным решением (по аналогии с дифференциальными уравнениями). Однородное решение — это точное решение уравнения (9.14), когда функция d(n), называемая управляющей функцией, равна 0 для всех n. Другими словами, однородное решение соответствует стоимости выполнения всех подзадач, если их можно объединить "бесплатно".
С другой стороны, второе выражение формулы (9.16) соответствует стоимости создания подзадач и комбинирования их результатов. Назовем это выражение частным решением (также по аналогии с теорией дифференциальных уравнений). Частное решение зависит как от управляющей функции, так и от количества и размера подзадач.
Существует практическое правило: если однородное решение больше управляющей функции, то частное решение имеет тот же порядок роста, что и однородное решение. Если же управляющая функция растет на порядок (для некоторого >0) быстрее однородного решения, тогда частное решение имеет такой же порядок роста, как и управляющая функция. Когда управляющая функция имеет с однородным решением одинаковый порядок роста или растет не медленнее, чем log^kn для некоторого k, тогда частное решение растет как управляющая функция, умноженная на logn.
При исследовании реализации любого алгоритма важно распознать, когда однородное решение будет больше управляющей функции, так как в этом случае любой более быстрый способ объединения подзадач не окажет существенного влияния на эффективность всего алгоритма. В этой ситуации для ускорения выполнения алгоритма надо или уменьшить количество подзадач, или уменьшить их размер. Только это может привести к тому, что однородное решение будет меньше общего времени выполнения алгоритма.
Если управляющая функция превышает однородное решение, тогда надо попытаться уменьшить эту функцию. Например, в случае процедуры mergesort, где а=b=2 и d(n)=сn, мы видели, что частное решение имеет порядок О(n logn). Если сделать функцию d(n) растущей медленнее, чем линейная, например как n^0,9, тогда, как мы увидим далее, частное решение будет расти медленнее, чем линейная функция, и общее время выполнения алгоритма будет иметь порядок О(n), такой же, как и однородное решение.