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

return(L); else begin

разбиение L на две части LI и L2, каждая длиной л/2; retum(merge(niergesort(Ll, п/2) , {mergesort(L2 , п/2] ) ) ;

end; { mergesort }

Обозначим через Т(п) время выполнения процедуры mergesort в самом худшем случае. Анализируя листинг 9.1, мокно записать следующее рекуррентное неравенство, ограничивающее сверху Т(пу.

[с., если ц = 1,

{2Т(п / 2)+сп, еслип > 1.

В неравенствах (9.1) константа Cj соответствует фиксированному количеству шагов, выполняемых алгоритмом над списком L длиной 1. Если и > 1, время выполнения процедуры mergesort мокно разбить на две части. Первая часть состоит из проверки того, что п * ], разбиения списка L на две равные части и вызова процедуры merge. Эти три операции требуют или фиксированного времени (проверка п ф 1), или пропорционального п - разбиение списка L и выполнение процедуры merge. Поэтому можно выбрать такую константу Сг. что время выполнения этой части процедуры mergesort будет ограничено величиной сгл. Вторая часть процедуры mergesort состоит из двух рекурсивных вызовов этой процедуры для списков длины п/2, которые требуют времени 2Т(п/2). Отсюда получаем второе неравенство (9.1).

Отметим, что соотношение (9.1) применимо только тогда, когда п четно. Следовательно, формулу для верхней границы Т(п) в замкнутой форме (т.е. в таком виде, когда формула для Т(п) не включает никаких выражений Т(т) для т < п) можно получить только в случае, если п является степенью числа 2. Но если известна формула для 7(п)тогда, когда п является степенью числа 2, то можно оценить Т(п) для любых п. Например, для практически всех алгоритмов можно предполагать, что значение Т(п) заключено между 7(2)и 7(2*),если п лежит между 2 и 2*, Более того, нетрудно показать, что в (9.1) выражение 27(п) можно заменить на Т((п+ 1)/2) -i- Т((п - 1)/2) для нечетных и > 1. Таким образом мокно найти решение рекуррентного соотношения в замкнутой форме для любых п.

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

Существуют три различных подхода к решению рекуррентных соотношений.

1. Нахождение функции f(n), которая мажорировала бы 7(л)для всех значений п (т.е. для всех га > 1 должно выполняться неравенство Т(п) < f(n)). Иногда сначала мы будем определять только вид функции f(n), предполагая, что она зависит от некоторых пока неопределенных параметров (например, /(л) = ап, где а - неопределенный параметр), затем подбираются такие значения параметров, чтобы для всех значений п выполнялось неравенство Т(п) < f(n).

2. В рекуррентном соотношении в правую часть последовательно подставляются выражения для Т{т), т < п, так, чтобы исключить из правой части все выражения Т(т)для m > 1, оставляя только 7(1). Поскольку 7(1) всегда является константой, то в результате получим формулу для Т(п), содержащую только га и константы. Такая формула и называется "замкнутой формой" для Т(п).

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

В этом разделе рассмотрим первых два подхода. 9.3. РЕШЕНИЕ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ 267



Оценка решений рекуррентных соотношений

Пример 9.1. Рассмотрим первый описанный выше подход на примере соотношения (9.1). Предположим, что Т(п)- an logn, где а - пока не определенный параметр. Подставляя п = 1, видим, что эта оценка "не работает", так как при п = 1 выражение an logn равно О, независимо от значения а. Попробуем применить другую функцию: Т(п) = an logn -i- Ь. При п = 1 эта оценка "работает", если положить Ъ > су.

В соответствии с методом математической индукции предполагаем, что для всех к < п выполняется неравенство

Т{к)< ак logk + b, (9.2)

и попытаемся доказать, что Т(п) < an logn + b.

Пусть га > 2. Из неравенств (9.1) имеем Т(п) < 2Т(п/2) + СзП. Полагая к - л/2, используем в последнем неравенстве оценку (9.2). Получаем

Т(п) < 2 а -log- + 6 V сп = V 2 2 ;

=anlogn-ап+сп + 2Ь< anlogn +b. (9.3)

Последнее неравенство получено в предположении, что а > с2+ Ь.

Таким образом, видим, что будет справедлива оценка Т(п)< an logn -i- 6, если будут выполняться неравенства b > Су и а > с2 + Ь. В данном случае можно удовлетворить этим неравенствам, если положить b = Су п а = су + Отсюда мы заключаем, что для всех п > 1 выполняется неравенство

Т(п) < (ci + с2)п logn + Су. (9.4)

Другими словами, Т(п) имеет порядок 0(п logn). D

Исходя из рассмотренного примера, сделаем два замечания. Во-первых, если мы предполагаем, что Т(п) имеет порядок 0(f(n)), но по индукции мы не можем доказать неравенства Т{п) < cf(n), то это еше не значит, что Т(п) Ф 0(f(n)). Возможно, надо просто добавить константу к функции с/(п), например можно попытаться доказать неравенство Т(п) < cf(n) - 1!

Во-вторых, мы не определили точной асимптотической степени роста оценочной функции f(n), мы только показали, что она растет не быстрее, чем 0(п logn). Если мы возьмем в качестве оценки более медленно растушие функции, например, такие как f(n) - an или f(n) = an log logn, то не сможем доказать, что Т(п) < f(n). Но в чем причина этого: неверный метод доказательства, или для данного алгоритма в принципе невозможна оценочная функция с меньшей степенью роста? Чтобы ответить на этот вопрос, надо подробнее проанализировать исследуемый алгоритм и рассмотреть время выполнения в самом худшем случае. Для нашей процедуры mergesort надо показать, что действительно время выполнения равно Q(n logn). Фактически мы показали, что время выполнения процедуры не превосходит сп logn для любых входных данных, но не для "самых плохих" входных данных. Случай возможных "самых плохих" входных данных мы оставляем в качестве упражнения.

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

П1) = с,

Т(п)< g{T(n/2), п)для п > 1. (9.5)

Отметим, что соотношение (9.5) обобшает соотношение (9.1), которое получается из (9.5), если положить g(x, у) = 2х + сзу. Конечно, возможны еше более обшие соотношения, чем (9.5). Например, функция g может включать в себя все значения Т(п - 1), Т(п - 2), Т(1), а не только Т(п/2). Также могут быть заданы значения для Т(1), Т(2), Т(к)и рекуррентное соотношение, которое применимо только для п > к. Читатель может самостоятельно попробовать приме-



нить к этим обобщенным рекуррентным соотношениям описанный выше метод оценки решения этих соотношений.

Вернемся к соотношению (9.5). Предположим, что выбранная оценочная функция f{ai,,.., ay, га) зависит от параметров ci, Uj, нам надо доказать индукцией по п, что Т(п) <f(ai, aj,n). (В примере 9.1 /(«ь Ла, га)= ап logn + аг, параметры ai и az обозначены как а и Ь.) Для того чтобы оценка Т(п) < f(ai, uj, га) была справедливой для всех и > 1, надо найти такие значения параметров ai, а,, чтобы выполнялись неравенства

flu!.....а„ 1)й с,

/(fti ..... а,та)> giKa,..., aj, та/2), га). (9.6)

В соответствии с методом математической индукции можно подставить функцию / вместо Тъ правую часть неравенства (9.5). Получаем

Т(п)< g(f(au-, а„ та/2), та). (9.7)

Если неравенство (9.6) выполняется (уже подобраны соответствующие значения параметров), то, применив его в (9.7), будем иметь то, что требуется доказать: T{n)<f(ai, ay, га).

В примере 9.1 мы имели g(x, у) = 2х + су и /(ai, аз, га) = a-ji logn -i- аг- Параметры ai и a-i надо подобрать так, чтобы выполнялись неравенства

/(ai.aa, 1) > Ci,

/(ai, ai, га) = ап logra -Ь aj > 2 Oj -log - + + cji.

V 2 2 ;

Для этого достаточно положить аг = сж ау = Су + с.

Оценка решения рекуррентного соотношения методом подстановки

Если мы не знаем вида оценочной функции или не уверены в том, что выбранная оценочная функция будет наилучшей границей для Т{п), то можно применить подход, который в принципе всегда позволяет получить точное решение для Т(л), хотя на практике он часто приводит к решению в виде достаточно сложных сумм, от которых не всегда удается освободиться. Рассмотрим этот подход на примере рекуррентного соотношения (9.1). Заменим в этом соотношении га на га/2, получим

Г(л/2) < 27(п/4) + сгп/2. (9.8)

Подставляя правую часть неравенства (9.8) вместо Т(п/2)в неравенство (9.1), будем иметь

Т(п)< 2(2Г(п/4) + c-n/Z) + Сгп = 4Г(п/4) + 2с2П. (9.9)

Аналогично, заменяя в неравенстве (9.1) га на га/4, получаем оценку для 7(л/4): Т(л/4) < 2T(n/S) + С2Л/4. Подставляя эту оценку в неравенство (9.9), получаем

Т(п) < 87(л/8) -i- ЗсзЛ. (9.10)

Надеемся, читатель понял принцип подстановки. Индукцией по ; для любого ; можно получить следующее соотношение:

Т(п) < 2Т{п/2)+ ic-iti. (9.11)

Предположим, что га является степенью числа 2, например га = 2*. Тогда при i = к в правой части неравенства (9.11) будет стоять Г(1):

Г(л) < 2*7(1) + ксгп. (9.12)

Поскольку га = 2, то к = logra. Так как (l) < ci, то из (9.12) следует, что

Т(п) < с1п+с2п logra. (9.13)

Неравенство (9.13) показывает верхнюю границу для (л), это и доказывает, что Т(п) имеет порядок роста не более 0(п logn).





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.0019