Структуры данных и алгоритмы (1021739), страница 70
Текст из файла (страница 70)
Общее решение большого класса рекуррентныхуравненийРассмотрим решение рекуррентных соотношений, когда исходную задачу размерап можно разделить на а подзадач каждую размера п/Ь. Для определенности будемсчитать, что выполнение задачи размера 1 требует одну единицу времени и что время"сборки" подзадач, составляющих исходную задачу размера п, требует d(n) единицвремени. В примере процедуры mergesort а = Ь = 2 и d(n) = c2n/Ci в единицах с\.
Тогда, если обозначить через Т(п) время выполнения задачи размера п, будем иметьТ(1) = 1,Т(п) = аТ(п/Ъ) + d(ra).(9.14)Отметим, что соотношение (9.14) можно применить только тогда, когда га является целой степенью числа Ь. Но если функция Т(п) достаточно гладкая, то решение,полученное в предположении, что га является целой степенью числа Ь, можно будетраспространить на другие значения п.Заметим также, что в (9.14) мы имеем уравнение, тогда как в (9.1) имели неравенство.
Причина заключается в том, что в (9.14) используется пока произвольнаяфункция d(n), поэтому мы имеем право записать точное равенство. А в (9.1) выражение с2га соответствует времени выполнения операции слияния списков в самом худшем случае и поэтому является верхней оценкой; фактическое время выполненияпроцедуры mergesort на входных данных размера га может быть меньше2Г(л/2) + czra. С другой стороны, не имеет значения, используем ли мы в рекуррентных соотношениях знак равенства или знак неравенства, поскольку мы ищем тольковерхнюю границу времени выполнения в самом худшем случае.Для решения уравнения (9.14) применим метод подстановки, рассмотренный впредыдущем разделе. Итак, подставим в (9.14) вместо га выражение п/Ь1:Подставляя в (9.14) равенства (9.15) последовательно для i — 1, 2, ..., получимТЫ - a r i.„(„T'fil+.ij'i )!+<«») , a'rj'i+=...=«<r^J+I«^J.л•'Если, как мы предположили, га = &*, тогда при i = k T(n/bk) = T(l) = 1 и мы получаем формулуt-iТ(п) - а" + ]Ta'd(&*-')(9.16)Так как k = logbn, то первое выражение в (9.16) можно записать как а'0"'" или,что эквивалентно, как ra'°f'°.
Таким образом, это выражение обозначает га в степени, которая зависит от а и Ь. Например, в случае процедуры mergesort а — Ь = 2,поэтому первое выражение равно просто га. В общем случае, чем больше а (т.е. надо решить большее количество подзадач), тем больший показатель степени га. Прибольших значениях Ь (чем больше Ь, тем меньше размер подзадач) показатель степени га будет меньше.270ГЛАВА 9. МЕТОДЫ АНАЛИЗА АЛГОРИТМОВОднородные и частные решенияИнтересно исследовать, какова роль обоих выражений в формуле (9.16).
Первоевыражение а* или га1"*'" называется однородным решением (по аналогии с дифференциальными уравнениями). Однородное решение — это точное решение уравнения(9.14), когда функция d(n), называемая управляющей функцией, равна 0 для всех п.Другими словами, однородное решение соответствует стоимости выполнения всехподзадач, если их можно объединить "бесплатно".С другой стороны, второе выражение формулы (9.16) соответствует стоимости создания подзадач и комбинирования их результатов.
Назовем это выражение частнымрешением (также по аналогии с теорией дифференциальных уравнений). Частное решение зависит как от управляющей функции, так и от количества и размера подзадач.Существует практическое правило: если однородное решение больше управляющейфункции, то частное решение имеет тот же порядок роста, что и однородное решение.Если же управляющая функция растет на порядок ле (для некоторого е > 0) быстрееоднородного решения, тогда частное решение имеет такой же порядок роста, как иуправляющая функция.
Когда управляющая функция имеет с однородным решениемодинаковый порядок роста или растет не медленнее, чем log'ra для некоторого k, тогдачастное решение растет как управляющая функция, умноженная на log л.При исследовании реализации любого алгоритма важно распознать, когда однородноерешение будет больше управляющей функции, так как в этом случае любой более быстрый способ объединения подзадач не окажет существенного влияния на эффективностьвсего алгоритма.
В этой ситуации для ускорения выполнения алгоритма надо илиуменьшить количество подзадач, или уменьшить их размер. Только это может привести ктому, что однородное решение будет меньше общего времени выполнения алгоритма.Если управляющая функция превышает однородное решение, тогда надо попытаться уменьшить эту функцию. Например, в случае процедуры mergesort, где а= b = 2 и d(n) = сп, мы видели, что частное решение имеет порядок О(п logn). Еслисделать функцию d(ri) растущей медленнее, чем линейная, например как п , тогда,как мы увидим далее, частное решение будет расти медленнее, чем линейная функция, и общее время выполнения алгоритма будет иметь порядок О(п), такой же, каки однородное решение.1Мультипликативные функцииЧастное решение в формуле (9.16) оценить достаточно трудно, даже если известен .вид функции d(n). Но для определенного, достаточно широкого класса функций d(n)можно найти точное решение (9.16).
Будем говорить, что функция f целочисленногоаргумента называется мультипликативной, если для всех положительных целыхчисел х и у справедливо равенство f(xy) — f(x)f(y).Пример 9.2. Для нас наибольший интерес представляют мультипликативныефункции вида па, где а — некоторая положительная константа. Чтобы показать,что функция /(n) = ntt является мультипликативной, достаточно заметить, чтоПусть в (9.16) функция d(n) является мультипликативной, тогда d(b ') = (d(b)) '.В этом случае частное решение запишется в следующем виде:d(b)d(b)1Но в случае процедуры mergesort нельзя надеяться, что найдется способ слияния двухсписков из п/2 элементов за время, меньшее по порядку, чем линейное, поскольку здесь в любом случае необходимо просмотреть все п элементов.9.4.
ОБЩЕЕ РЕШЕНИЕ БОЛЬШОГО КЛАССА РЕКУРРЕНТНЫХ УРАВНЕНИЙ271Теперь необходимо рассмотреть три ситуации, зависящие от того, будет ли параметр а больше, меньше или равен d(b).1.2.3.Если а > d(b), тогда последнее выражение в (9.17) имеет порядок O(ak), которыйможно переписать как га'"*"1, поскольку k = log<,n. В этом случае частное и однородные решения имеют одинаковый порядок роста, который зависит только от аи Ъ, но не от управляющей функции. Поэтому в данной ситуации уменьшениевремени выполнения алгоритма можно достичь путем уменьшения а или увеличения Ь, уменьшение порядка роста функции d(n) здесь не поможет.Если а < d(b), тогда последнее Выражение в (9.17) имеет порядок O(d(b)k), или,что то же самое, O(n'°e'd((')). В этом случае частное решение превышает однородное.
Поэтому для уменьшения времени выполнения алгоритма можно манипулировать как функцией d(n), так и параметрами а и Ь. В важном частном случае,когда d(ri) = га™, d(b) будет равно Ьа и \ogb(ba) = а. Тогда частное решение имеетпорядок О(па) или O(d(n)).Если а = d(b), тогда надо пересмотреть решение (9.17), поскольку в данном случае нельзя применять формулу суммирования членов геометрической прогрессии.
В этой ситуации суммируем следующим образом:log, п.(9.18)Поскольку а = d(b), то частное решение (9.18) равно однородному решению, умноженному на logt,n. Здесь опять частное решение превосходит однородное. В частном случае, когда d(n) = па, решение (9.18) имеет порядок О(га™ logn).Пример 9.3. Рассмотрим следующие рекуррентные уравнения с начальным значением Г(1) = 1.1.2.3.Т(п) = 4Г(п/2) + п.Т(п) = 4Т(п/2) + п2.Т(п) = 4Т(п/2) + ге3.В каждом уравнении а = 4 и Ь = 2, следовательно, однородное решение равно га2.В уравнении (1) d(n) — п, поэтому d(b) = 2.
Поскольку а = 4 > d(b), то частное решение также имеет порядок га2. Поэтому здесь Т(п) = О(п2),В уравнении (3) d(n) = га2, d(b) = 8 и а < d(b). Тогда частное решение имеет порядок O(n}°f"dw) = О(п3) и Т(п) в этом уравнении также равно О(га3).В уравнении (2) d(b) = 4 = а, поэтому решение дается формулой (9.18). Здесь какчастное решение, так и Т(п) имеют порядок О(га2 logra). ПДругие управляющие функцииСуществуют другие типы управляющих функций, отличные от мультипликативных, которые позволяют получить замкнутую форму решения (9.16). Мы рассмотримтолько два примера таких функций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
