Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 23

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 23)

4.3. Метод подстановки решения рекуррентных соотношений Теперь, когда вы познакомились с описанием времени работы алгоритмов "разделяй и властвуй" рекуррентными соотношениями, рассмотрим способы решения таких рекуррентных соотношений. В этом разделе начнем рассмотрение с метода подстановки. Метод подстановки для решения рекуррентных соотношений состоит из двух шагов: 1.

делается предположение о виде решения; 2. с помощью метода математической индукции определяются константы и доказывается, что решение правильное. Название "метод подстановки" связано с тем, что мы подставляем предполагаемое решение вместо функции при применении гипотезы индукции для меньших значений. Это мощный метод, но для его применения нужно суметь сделать предположение о виде решения. Метод подстановки можно применять для определения либо верхней, либо нижней границы рекуррентного соотношения.

В качестве примера определим верхнюю границу рекуррентного соотношения Т(п) = 2Т((п/21') + и, (4.19) подобного соотношениям (4.3) и (4.4). Мы предполагаем, что решение имеет вид Т(п) = 0(п!я и). Наш метод заключается в доказательстве того, что при подходящем выборе константы с ) О выполняется неравенство Т(п) < си 1я и.

Начнем с того, что предположим справедливость этого неравенства для всех положительных ги < п, в частности для ги = '1п/2), что дает Т(~ п/2~) < с (и/21 1б((п/2~). 109 Глава 4 Разделяй и влааввуй Подстановка в рекуррентное соотношение приводит к Т(п) < 2(с (п/2) 1й(1п/2))) + п < си 1б(п/2) + п = сп 1я и — сп 1я 2 + п = си1кп — оп+ п < си)яп, где последний шаг выполняется при с > 1. Теперь, согласно методу математической индукции, необходимо доказать, что наше решение справедливо для граничных условий. Обычно для этого достаточно показать, что граничные условия являются подходящей базой для доказательства по индукции. В рекуррентном соотношении (4.19) необходимо доказать, что константу с можно выбрать достаточно большой для того, чтобы соотношение Т(п) < си1яп было справедливо и для граничных условий.

Такое требование иногда приводит к проблемам. Предположим, например, что Т(1) = 1 — единственное граничное условие рассматриваемого рекуррентного соотношения. Далее, для и = 1 соотношение Т(п) < сп 1я и дает нам Т(1) < с 1 1я 1 = О, что противоречит условию Т(1) = 1. Следовательно, данный базис индукции нашего доказательства не выполняется. Эту сложность, возникающую при доказательстве предположения индукции для указанного граничного условия, легко обойти. Например, в рекуррентном соотношении (4.19) можно воспользоваться преимуществами асимптотических обозначений, требующих доказать неравенство Т(п) < оп1я и для и > по, где пр — выбранная нами константа. Идея по устранению возникшей проблемы заключается в том, чтобы в доказательстве по методу математической индукции не учитывать граничное условие Т(1) = 1.

Обратите внимание, что при и > 3 рассматриваемое рекуррентное соотношение явным образом от Т(1) не зависит. Таким образом, выбрав по = 2, в качестве базы индукции можно рассматривать не Т(1), а Т(2) и Т(З). Заметим, что здесь делается различие между базой рекуррентного соотношения (п = 1) и базой индукции (и = 2 и и = 3).

Из рекуррентного соотношения следует, что Т(2) = 4, а Т(З) = 5. Теперь доказательство по методу математической индукции соотношения Т(п) < сп1яп для некоторой константы с > 1 можно завершить, выбрав ее достаточно большой для того, чтобы были справедливы неравенства Т(2) < с2 1л 2 и Т(3) < с31я 3. Оказывается, что для этого достаточно выбрать с > 2. В большинстве рекуррентных соотношений, которые нам предстоит рассмотреть, легко расширить граничные условия таким образом, чтобы гипотеза индукции оказалась верна для малых п. Как упщагь решение К сожалению, не существует общего способа„позволяющего угадать правильное решение рекуррентного соотношения.

Для этого требуются опыт, удача и творческое мышление. К счастью, существуют определенные эвристические приемы, которые могут помочь сделать правильную догадку. Кроме того, для Часть 1 Оаиааы ПО получения предполагаемого вида решения можно воспользоваться деревьями рекурсии, с которыми мы познакомимся в разделе 4.4.

Если рекуррентное соотношение подобно тому, которое мы уже рассматривали, то разумно предположить, что решения этих соотношений будут похожими. Например, рассмотрим рекуррентное соотношение Т(п) = 2Т((п/2) + 17) + п, которое выглядит более сложным, поскольку в аргументе функции Т в его правой части добавлено слагаемое "17". Однако интуитивно понятно, что это дополнительное слагаемое не может сильно повлиять на асимптотическое поведение решения. При достаточно больших п разность между (п/2) и (и/2) + 17 невелика: оба эти числа приблизительно равны половине числа и.

Следовательно, можно предположить, что Т(п) = О(п 1яп); проверить корректность этого предположения можно методом подстановки (см. упр. 4.3.6). Другой способ найти решение — выполнить грубую оценку его верхней и нижней границ, а затем свести неопределенность до минимальной. Например, в рекуррентном соотношении (4.19) в качестве начальной нижней границы можно было бы выбрать Т(п) = П(п), поскольку в нем содержится слагаемое и; можно также доказать, что грубой верхней границей является Т(п) = 0(п~). Далее верхняя граница постепенно понижается, а нижняя — повышается до тех пор, пока не будет получено правильное асимптотическое поведение решения Т(п) = Й(п 1я и). Тонкие нюансы Иногда сделать правильное предположение об асимптотическом поведении решения рекуррентного соотношения можно, но при этом возникают трудности, связанные с выполнением доказательства по методу математической индукции.

Обычно проблема заключается в том, что выбрано недостаточно сильное предположение индукции, которое не позволяет доказать точную границу. Натолкнувшись на такое препятствие, пересмотрите предположение индукции, избавившись от членов низшего порядка. При этом часто удается провести строгое математическое доказательство. Рассмотрим рекуррентное соотношение Т(п) = Т((п/2) ) + Т( (п/2) ) + 1 . Можно предположить, что его решением является Т(п) = 0(п), и попытаться показать, что Т(п) < сп для подходящего выбора константы с. Подставив предполагаемое решение в рекуррентное соотношение, получим выражение Т(п) < с(п/2) + с(п/2) + 1 =си+1, из которого не следует Т(п) < сп ни для какого выбора с.

Можно попытаться сделать другие предположения, например о том, что решение — Т(и) = 0(и ). Рлатз К Разделяй и властвуй Хотя это предположение н можно доказать, наше первоначальное предположение вполне корректно. Однако чтобы это показать„необходимо выбрать более сильную гипотезу индукции. Интуитивно понятно, что наша догадка была почти правильной: мы ошиблись всего лишь на константу, равную 1, т.е.

на величину низшего порядка. Тем не менее математическая индукция не работает, если в предположении индукции допущена даже такая, казалось бы, незначительная ошибка. Эту трудность можно преодолеть, если вычесть из первоначального предположения член низшего порядка. Таким образом, теперь гипотеза индукции имеет вид Т(п) < сп — з1, где 6 > Π— константа. Теперь мы имеем Т(п) < (с 1п/2) — з1) + (с (и/2) — с1) + 1 = сп — 2с1+ 1 < сп — с1, юторое справедливо при з1 > 1.

Как и раньше, чтобы выполнялись граничные условия, юнстанту с необходимо выбрать достаточно большой. Идея вычитания члена более низкого порядка может показаться противоречащей интуитивным представлениям. Ведь если предположение не сработало, его следует ослабить, не так ли? Не обязательно! При доказательстве верхней границы по индукции в действительности может оказаться сложнее доказать более слабую верхнюю границу, поскольку при ее доказательстве мы вынуждены использовать в доказательстве ее же. В наших примерах, в юторых рекуррентное соотношение имеет более одного рекурсивного члена, мы вычитаем член более низкого порядка из предложенной границы по одному разу для каждого рекурсивного члена.

В приведенном выше примере константа д вычитается дважды, один раз для члена Т( 1п/2) ) и второй — для члена Т( ~п/21 ). В результате получается неравенство Т(п) < сп — 2з1+ 1, и можно легю найти значения с(, которые делают сп — 2с1 + 1 меньшим или равным сп — з1. Остерегайтесь ошибок Используя асимптотические обозначения, легко допустить ошибку. Например, для рекуррентного соотношения (4.19) легко "доказать'*, что Т(п) = 0(п), предположив, что Т(п) < сп, а затем рассуждая следующим образом: Т(п) < 2(с(п/2)) + п < оп+и = 0(п), ~ ОизибкаИ поскольку с представляет собой константу. Ошибка заключается в том, что не была доказана гипотеза индукции в точном виде, т.е.

что Т(п) < сп. Таким образом, мы неявно доказали, что Т(п) < сп, в то время как мы хотели показать, что Т(п) = 0(п). часть к Основы Замена переменных Иногда с помощью небольших алгебраических преобразований удается добиться того, что неизвестное рекуррентное соотношение становится похожим на то, с которым мы уже знакомы. Например, рассмотрим рекуррентное соотношение Т(п) = 2Т((~/п!) + 1кп, которое выглядит довольно сложным. Однако его можно упростить, выполнив замену переменных.

Характеристики

Список файлов книги