Структуры данных и алгоритмы (1021739), страница 69
Текст из файла (страница 69)
Например, в предыдущей главе мы анализировали среднее времявыполнения алгоритма быстрой сортировки в предположении, что все первоначальные упорядочения входных последовательностей равновероятны.I.9.2. Анализ рекурсивных программВ главе 1 мы показали методы анализа времени выполнения программ, не использующих рекурсивных вызовов. Анализ рекурсивных программ значительносложнее и, как правило, требует решения дифференциальных уравнений.
Мы будемиспользовать другие методы, которые похожи на методы решения дифференциальных уравнений, и даже позаимствуем их терминологию.Сначала рассмотрим пример процедуры сортировки (листинг 9.1). Эта процедурафункция mergesort (сортировка слиянием) в качестве входных данных использует списокэлементов длиной п и возвращает этот список отсортированным (выходные данные). Этафункция использует также процедуру merge (слияние), у которой входными данными являются два отсортированных списка LI и L2- Процедура merge(Llt L2) просматривает этисписки поэлементно, начиная с наибольших элементов. На каждом шаге наибольшийэлемент из двух сравниваемых (наибольшие элементы из списков L\ и L2) удаляется изсвоего списка и помещается в выходные данные. В результате получается один отсортированный список, содержащий все элементы из списков LI и L2.
Детали выполненияпроцедуры merge сейчас для нас не имеют значения, сортировка слиянием подробно рассмотрена в главе 11. Сейчас для нас важно только то, что процедура merge на спискахдлиной п/2 выполняется за время порядка О(л).Листинг 9.1. Рекурсивная процедура сортировки слияниемfunction mergesort ( L: LIST; n: integer ): LIST{ L — список типа LIST длиной л.Предполагается, что л является степенью числа 2 }varLI, L2: LISTbeginif л = 1 then266ГЛАВА 9. МЕТОДЫ АНАЛИЗА АЛГОРИТМОВreturn(L);else beginразбиение L на две части LI и L2, каждая длиной л/2;return(merge(mergesort(LI,n/2),endend; { mergesort }(mergesort(L2,л/2)));Обозначим через Т(п) время выполнения процедуры mergesort в самом худшемслучае. Анализируя листинг 9.1, можно записать следующее рекуррентное неравенство, ограничивающее сверху Т(п):Jq, если п = 1,~ [2Т(п/2) + с2п, если п > 1.В неравенствах (9.1) константа c t соответствует фиксированному количеству шагов, выполняемых алгоритмом над списком L длиной 1.
Если п > 1, время выполнения процедуры mergesort можно разбить на две части. Первая часть состоит из проверки того, что п Ф 1, разбиения списка L на две равные части и вызова процедурыmerge. Эти три операции требуют или фиксированного времени (проверка п Ф 1), илипропорционального п — разбиение списка L и выполнение процедуры merge. Поэтому можно выбрать такую константу с2, что время выполнения этой части процедурыmergesort будет ограничено величиной с2п. Вторая часть процедуры mergesort состоитиз двух рекурсивных вызовов этой процедуры для списков длины п/2, которые требуют времени 2Т(п/2).
Отсюда получаем второе неравенство (9.1).Отметим, что соотношение (9.1) применимо только тогда, когда п четно. Следовательно, формулу для верхней границы Т(п) в замкнутой форме (т.е. в таком виде,когда формула для Т(п) не включает никаких выражений Т(т) для т < п) можнополучить только в случае, если п является степенью числа 2. Но если известна формула для Т(п) тогда, когда п является степенью числа 2, то можно оценить Т(п) длялюбых п. Например, для практически всех алгоритмов можно предполагать, что знаt+l1+1чение Т(п) заключено между Т(2') и T(2 ), если п лежит между 2' и 2 . Более того,нетрудно показать, что в (9.1) выражение 2Т(п) можно заменить наТ((п + 1)/2) + Т((п - 1)/2) для нечетных п > 1.
Таким образом можно найти решениерекуррентного соотношения в замкнутой форме для любых п.9.3. Решение рекуррентных соотношенийСуществуют три различных подхода к решению рекуррентных соотношений.1.Нахождение функции f(n), которая мажорировала бы Т(п) для всех значений п(т.е. для всех га > 1 должно выполняться неравенство Т(п) < f(n)).
Иногда сначаламы будем определять только вид функции /(л), предполагая, что она зависит отнекоторых пока неопределенных параметров (например, /(га) = an2, где а — неопределенный параметр), затем подбираются такие значения параметров, чтобыдля всех значений п выполнялось неравенство Т(п) < f(n).2. В рекуррентном соотношении в правую часть последовательно подставляютсявыражения для Т(т), т < п, так, чтобы исключить из правой части все выражения Т(т) для т > 1, оставляя только Г(1).
Поскольку Т(1) всегда является константой, то в результате получим формулу для Т(п), содержащую только га иконстанты. Такая формула и называется "замкнутой формой" для Т(п).3. Третий подход заключается в использовании общих решений определенных рекуррентных соотношений, приведенных в этой главе или взятых из других источников (см. библиографические примечания).В этом разделе рассмотрим первых два подхода.9.3.
РЕШЕНИЕ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ267Оценка решений рекуррентных соотношенийПример 9.1. Рассмотрим первый описанный выше подход на примере соотношения (9.1). Предположим, что Т(п) — an log/i, где а — пока не определенный параметр. Подставляя п = 1, видим, что эта оценка "не работает", так как при п = 1 выражение an logn равно 0, независимо от значения а. Попробуем применить другуюфункцию: Т(п) = an logn + Ь. При п = 1 эта оценка "работает", если положить Ь > сг.В соответствии с методом математической индукции предполагаем, что для всехk < п выполняется неравенствоT(k) < ak logfc + b,(9.2)и попытаемся доказать, что Т(п) < an logn + b.Пусть га > 2.
Из неравенств (9.1) имеем Т(п) < 2Т(п/2) + с^п. Полагая k — л/2, используем в последнем неравенстве оценку (9.2). ПолучаемТ(п) < 2 a —log —+ 6 + с2п =2\ 2J= anlogn — an + c2n + 2b < аи logn + b.(9.3)Последнее неравенство получено в предположении, что а > с2 + Ь.Таким образом, видим, что будет справедлива оценка Т(п) < an logn + 6, если будут выполняться неравенства b > сг и а > eg + b. В данном случае можно удовлетворить этим неравенствам, если положить b = c t и а = cj + Сз. Отсюда мы заключаем,что для всех п > 1 выполняется неравенствоТ(п) < (а + сг)п logn + ci.(9.4)Другими словами, Т(п) имеет порядок O(n logn). DИсходя из рассмотренного примера, сделаем два замечания. Во-первых, если мыпредполагаем, что Т(п) имеет порядок О(/(п)), но по индукции мы не можем доказатьнеравенства Т(п) < cf(n), то это еще не значит, что Т(п) # O(f(n)).
Возможно, надопросто добавить константу к функции cf(n), например можно попытаться доказатьнеравенство T(n) < cf(n) — 1!Во-вторых, мы не определили точной асимптотической степени роста оценочнойфункции f(n), мы только показали, что она растет не быстрее, чем О(п logn).
Еслимы возьмем в качестве оценки более медленно растущие функции, например, такиекак f(n) — an или /(п) = an log logn, то не сможем доказать, что Т(п) < f(n). Но в чемпричина этого: неверный метод доказательства, или для данного алгоритма в принципе невозможна оценочная функция с меньшей степенью роста? Чтобы ответить наэтот вопрос, надо подробнее проанализировать исследуемый алгоритм и рассмотретьвремя выполнения в самом худшем случае.
Для нашей процедуры mergesort надо показать, что действительно время выполнения равно Q(n logn). Фактически мы показали, что время выполнения процедуры не превосходит en logn для любых входныхданных, но не для "самых плохих" входных данных. Случай возможных "самыхплохих" входных данных мы оставляем в качестве упражнения.Метод получения оценки решения рекуррентных соотношений, проиллюстрированный в примере 9.1, можно обобщить на некоторые другие функции, ограничивающиесверху время выполнения алгоритмов.
Пусть имеется рекуррентное соотношение7(1) = с,Т(п) < g(T(n/2),n) для п > 1.(9.5)Отметим, что соотношение (9.5) обобщает соотношение (9.1), которое получается из (9.5), если положить g(x, у) = 2х + с2у. Конечно, возможны еще болееобщие соотношения, чем (9.5). Например, функция g может включать в себя всезначения Т(п - 1), Т(п - 2), ..., Т(1), а не только Т(п/2). Также могут быть заданы значения для Т(1), Т(2), ..., T(k) и рекуррентное соотношение, которое применимо только для п > k.
Читатель может самостоятельно попробовать приме268ГЛАВА 9. МЕТОДЫ АНАЛИЗА АЛГОРИТМОВнить к этим обобщенным рекуррентным соотношениям описанный выше методоценки решения этих соотношений.Вернемся к соотношению (9.5). Предположим, что выбранная оценочная функцияf(fli, ,.., a.j, га) зависит от параметров а\, ..., a.j, нам надо доказать индукцией по п, чтоТ(п) < f(ai, ..., dj, п).
(В примере 9.1 /(OL а2, га) = a^ra logn + а2, параметры аг и а2 обозначены как а и Ь.) Для того чтобы оценка Т(га) < /(аь ..., а,, га) была справедливой для всехп > 1, надо найти такие значения параметров а±, ..., о,, чтобы выполнялись неравенстваf(ai ..... 'а,, га) > g(f(alt .... ajtга/2),га).(9.6)В соответствии с методом математической индукции можно подставить функцию /вместо Т в правую часть неравенства (9.5). ПолучаемТ(п) < g(f(alt ..., а,,га/2),га).(9.7)Если неравенство (9.6) выполняется (уже подобраны соответствующие значения параметров), то, применив его в (9.7), будем иметь то, что требуется доказать: Т(п) < f(ui, ..., uj, га).В примере 9.1 мы имели g(x, у) = 2х + с2у и /(«ь о.2, га) = агп logra + а2. Параметры a t и а2 надо подобрать так, чтобы выполнялись неравенстваf(alt а2, 1) > сь/(аь а2, га) = ajre logra + a2 > 2 1аг ^ log -^ + а2 +с 2 га.V 2 2)Для этого достаточно положить а 2 = c t и Oi = ci + с2.Оценка решения рекуррентного соотношения методом подстановкиЕсли мы не знаем вида оценочной функции или не уверены в том, что выбраннаяоценочная функция будет наилучшей границей для Т(п), то можно применить подход, который в принципе всегда позволяет получить точное решение для Т(п), хотяна практике он часто приводит к решению в виде достаточно сложных сумм, от которых не всегда удается освободиться.
Рассмотрим этот подход на примере рекуррентного соотношения (9.1). Заменим в этом соотношении га на га/2, получимГ(га/2) < 2Г(га/4) + с 2 га/2.(9.8)Подставляя правую часть неравенства (9.8) вместо Т(п/2) в неравенство (9.1), будем иметьТ(п) < 2(2Г(га/4) + с 2 га/2) + С2га = 4Г(га/4) + 2с2га.(9.9)Аналогично, заменяя в неравенстве (9.1) га на га/4, получаем оценку для 7т(га/4):Т(га/4) < 2Т(л/8) + с2га/4. Подставляя эту оценку в неравенство (9.9), получаемТ(п) < 8Т(га/8) + Зс2га.(9.10)Надеемся, читатель понял принцип подстановки. Индукцией по i для любого iможно получить следующее соотношение:Т(п) < 2'T(n/2l) + ic2n.(9.11)Предположим, что га является степенью числа 2, например га = 2*.
Тогда при i = kв правой части неравенства (9.11) будет стоять Г(1):Г(га) < 2*Т(1) + kc2n.(9.12)Поскольку га = 2*, то k = logra. Так как Г(1) < сь то из (9.12) следует, чтоT(n) < Cjra + c2ra logra.(9.13)Неравенство (9.13) показывает верхнюю границу для Т(п), это и доказывает, чтоТ(п) имеет порядок роста не более О(п logn).9.3. РЕШЕНИЕ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ2699.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
