Главная Промышленная автоматика.

9.4. Общее решение большого класса рекуррентных уравнений

Рассмотрим решение рекуррентных соотношений, когда исходную задачу размера п можно разделить на а подзадач каждую размера п/Ь. Для определенности будем считать, что выполнение задачи размера 1 требует одну единицу времени и что время "сборкм" подзадач, составляющих исходную задачу размера п, требует d{n) единиц времени. В примере процедуры mergesort а = Ь = 2 и d{n) = сп/су в единицах Су. Тогда, если обозначить через Т(п) время выполнения задачи размера п, будем иметь

Т(1) = 1,

Т(п) = аТ(п/Ь) + d{n). (9.14)

Отметим, что соотношение (9.14) можно применить только тогда, когда га является целой степенью числа Ь. Но если функция Т(п) достаточно гладкая, то решение, полученное в предположении, что га является целой степенью числа Ь, можно будет распространить на другие значения п.

Заметим таюке, что в (9.14) мы имеем уравнение, тогда как в (9.1) имели неравенство. Причина заключается в том, что в (9.14) используется пока произвольная функция d(n), поэтому мы имеем право записать точное равенство. А в (9.1) выражение Сзл соответствует времени выполнения операции слияния списков в самом худшем случае и поэтому является верхней оценкой; фактическое время выполнения процедуры mergesort на входных данных размера га может быть меньше 2Т(п/2) + сп. С другой стороны, не имеет значения, используем ли мы в рекуррентных соотношениях знак равенства или знак неравенства, поскольку мы ищем только верхнюю границу времени выполнения в самом худшем случае.

Для решения уравнения (9.14) применим метод подстановки, рассмотренный в предыдущем разделе. Итак, подставим в (9.14) вместо га выражение п/Ь:

= оТ

Подставл5ш в (9.14) равенства (9.15) последовательно для / -

ты- аТ\ -

+ d{n) = а

+ ad

( п

+ ad

+ ad

(9-15)

2, получим + d(n) =

= ... = аТ

Если, как мы предположили, га = fc, тогда при / = к Т{п/ь)= 7(1)= 1 и мы получаем формулу

T(n)-a + ja>d(b"). (9.16)

Так как к = logjn, то первое выражение в (9.16) можно записать как а"*" или, что эквивалентно, как га°°. Таким образом, это выражение обозначает га в степени, которая зависит от а и Ь. Например, в случае процедуры mergesort а - Ь = 2, поэтому первое выражение равно просто га. В общем случае, чем больше а (т.е. надо решить большее количество подзадач), тем больший показатель степени га. При больших значениях b (чем больше Ь, тем меньше размер подзадач) показатель степени га будет меньше.



Однородные и частные решения

Интересно исследовать, какова роль обоих выражений в формуле (9.16). Первое выражение а* или га"*" называется однородным решением (по аналогии с дифференциальными уравнениями). Однородное решение - это точное решение уравнения (9.14), когда функция d(n), называемая управляющей функцией, равна О для всех п. Другими словами, однородное решение соответствует стоимости выполнения всех подзадач, если их можно объединить "бесплатно".

С другой стороны, второе выражение формулы (9.16) соответствует стоимости создания подзадач и комбинирования их результатов. Назовем это выражение частным решением (также по аналогии с теорией дифференциальных уравнений). Частное решение зависит как от управляюшей функции, так и от количества и размера подзадач. Сушествует практическое правило: если однородное решение больше управляюшей функции, то частное решение имеет тот же порядок роста, что и однородное решение. Если же управляюшая функция растет на порядок (для некоторого е > 0) быстрее однородного решения, тогда частное решение имеет такой же порядок роста, как и управляюшая функция. Когда управляюшая функция имеет с однородным решением одинаковый порядок роста или растет не медленнее, чем log*n для некоторого к, тогда частное решение растет как управляюшая функция, умноженная на logл.

При исследовании реализации любого алгоритма важно распознать, когда однородное решение будет больше управляюшей функции, так как в этом случае любой более быстрый способ обьединения подзадач не окажет сушественного влияния на эффективность всего алгоритма. В этой ситуации для ускорения выполнения алгоритма надо или уменьшить количество подзадач, или уменьшить их размер. Только это может привести к тому, что однородное решение будет меньше обшего времени выполнения алгоритма.

Если управляюшая функция превышает однородное решение, тогда надо попытаться уменьшить эту функцию. Например, в случае процедуры mergesort, где а = b = 2 и d(n) = СП, мы видели, что частное решение имеет порядок 0(п logn). Если сделать функцию d(n) растушей медленнее, чем линейная, например как п , тогда, как мы увидим далее, частное решение будет расти медленнее, чем линейная функция, и обшее время выполнения алгоритма будет иметь порядок 0(п), такой же, как и однородное решение.

Мультипликативные функции

Частное решение в формуле (9.16) оценить достаточно трудно, даже если известен . вид функции d(n). Но для определенного, достаточно широкого класса функций d(n) можно найти точное решение (9.16). Будем говорить, что функция / целочисленного аргумента называется мультипликативной, если для всех положительных целых чисел хну справедливо равенство f(xy) - f(x)f(y).

Пример 9.2. Для нас наибольший интерес представляют мультипликативные функции вида п", где а - некоторая положительная константа. Чтобы показать, что функция /(л) = л" является мультипликативной, достаточно заметить, что {хуГ = х"у". □

Пусть в (9.16) функция d(n) является мультипликативной, тогда d(b ) = (d(6)) . В этом случае частное решение запишется в следующем виде:

"Zidmr- = d(b)X

1.0 iro

d(b)

d(b)

- d{bf

(9.17)

d(b)

Ho в случае процедуры mergesort нельзя надеяться, что найдется способ слияния двух списков из л/2 элементов за время, меньшее по порядку, чем линейное, поскольку здесь в любом случае необходимо просмотреть все п элементов.



Теперь необходимо рассмотреть три ситуации, зависящие от того, будет ли параметр а больше, меньше или равен d(b).

1. Если а > d(b), тогда последнее выражение в (9.17) имеет порядок 0(а*), который можно переписать как га"*", поскольку к = logjn. В этом случае частное и однородные решения имеют одинаковый порядок роста, который зависит только от а и Ъ, но не от управляющей функции. Поэтому в данной ситуации уменьшение времени выполнения алгоритма можно достичь путем уменьшения а или увеличения Ь, уменьшение порядка роста функции d(n) здесь не поможет.

2. Если а < d(b), тогда последнее выражение в (9.17) имеет порядок 0(d(6)), или, что то же самое, 0(л°*""). В этом случае частное решение превышает однородное. Поэтому для уменьшения времени выполнения алгоритма можно манипулировать как функцией d{ri), так и параметрами а и Ь. В важном частном случае, когда d(n}= га™,d(b) будет равно Ь" и logi,(6")= а. Тогда частное решение имеет порядок 0(л") или 0(d(n)).

3. Если а = d(b), тогда надо пересмотреть решение (9.17), поскольку в данном случае нельзя применять формулу суммирования членов геометрической прогрессии. В этой ситуации суммируем следующим образом:

X(d(b))- = dibYji] = d(b)Xl -тк = n--Mogw. (9.18)

(Г. d(b) j , 0

Поскольку a = d(b), то частное решение (9.18) равно однородному решению, умноженному на logi,n. Здесь опять частное решение превосходит однородное. В частном случае, когда d{n) = п", решение (9.18) имеет порядок 0(п" logn).

Пример 9.3. Рассмотрим следующие рекуррентные уравнения с начальным значением Т(1) = 1.

1. Т{п)= 4Т{п/2) + п.

2. Т(п) = 4Т(п/2)+ п\

3. Т{п)= 4Т(п/2)+ ге.

В каждом уравнении а = 4 и b = 2, следовательно, однородное решение равно ral В уравнении (1) d(n) - п, поэтому d(b) = 2. Поскольку а = 4 > d(b), то частное решение также имеет порядок ral Поэтому здесь Т(п) = О(п).

В уравнении (3) d(n) = га d(b) = 8 и а < d(b). Тогда частное решение имеет порядок 0(п°*""")= О(п) и Т(п) в этом уравнении также равно О(л).

В уравнении (2) d(b) = 4 = а, поэтому решение дается формулой (9.18). Здесь как частное решение, так и 7(л)имеют порядок 0(п logn). П

Другие управляющие функции

Существуют другие типы управляющих функций, отличные от мультипликативных, которые позволяют получить замкнутую форму решения (9.16). Мы рассмотрим только два примера таких функций. В первом примере получаем небольшое обобщение мультипликативных функций, а именно, здесь рассматриваются мультипликативные функции, умноженные на константу, которая больше или равна единице. Во втором примере просто показан частный случай функции d(n), позволяющий получить замкнутую форму решения (9.16).

Пример 9.4. Рассмотрим следующее рекуррентное уравнение: Т(1) =1,

Т{п)= ЗПп/2) + 2п \





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 [86] 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0059