Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 22
Текст из файла (страница 22)
Граничные условия — еще один пример технических особенностей, которые обычно игнорируются. Поскольку время работы алгоритма с входными данными фиксированного размера выражается константой, то в рекуррентных соотношениях, описывающих время работы алгоритмов, для достаточно малых и обычно справедливо соотношение Т (и) = О (1). Поэтому для удобства граничные условия рекуррентных соотношений, как правило, опускаются и предполагается, что для малых п время работы алгоритма Т (и) является константой. Например, рекуррентное соотношение (4.1) обычно записывается как Т(п) = 2Т(7т/2) + О(п), (4.3) без явного указания значений Т (п) для малых и.
Причина состоит в том, что хотя изменение значения Т (1) приводит к изменению решения рекуррентного соотношения, это решение обычно изменяется не более, чем на постоянный множитель, а порядок роста остается неизменным. Формулируя и решая рекуррентные соотношения, мы часто опускаем граничные условия, а также тот факт, что аргументами неизвестных функций являются целые числа. Мы продвигаемся вперед без этих деталей, а потом выясняем, важны они или нег. Даже если технические детали, которые опускаются при анализе алгоритмов, несущественны, то важно убедиться, что они не влияют на порядок роста решения. В подобных рассуждениях помогает опыт, а также некоторые теоремы.
В этих теоремах формулируются условия, когда упомянутые детали не влияют на асимптотическое поведение рекуррентных соотношений, возникающих при анализе алгоритмов (см. теорему 4.1). Однако в данной главе мы не будем опускать технические детали, так как это позволит продемонстрировать некоторые тонкости, присущие методам решения рекуррентных соотношений.
Глава 4. Рекуррентные соотношения 4.1 Метод подстановки Метод подстановки, применяющийся для решения рекуррентных уравнений, состоит из двух этапов: 1. делается догадка о виде решения; 2. с помощью метода математической индукции определяются константы и доказывается, что решение правильное. Происхождение этого названия объясняется тем, что предполагаемое решение подставляется в рекуррентное уравнение. Это мощный метод, но он применим только в тех случаях, когда легко сделать догадку о виде решения. Метод подстановки можно применять для определения либо верхней, либо нижней границ рекурреитного соотношения. В качестве примера определим верхнюю границу рекуррентного соотношения Т (п) = 2Т ( 1п/21') + и, (4.4) подобного соотношениям (4.2) и (4.3). Мы предполагаем, что решение имеет вид Т (и) = О (п!кп). Наш метод заключается в доказательстве того, что при подходящем выборе константы с > О выполняется неравенство Т (и) < сп )кп.
Начнем с того, что предположим справедливость этого неравенства для величины 1п/21, т.е. что выполняется соотношение Т(1п/21') < с 1и/21 1б((п/2)). После подстановки данного выражения в рекуррентное соотношение получаем: Т(п) < 2(с~п/2) 1к((и/2))) + п < < сп !к (и/2) + п = = сп 1к п — сп 1к 2 + и = = оп1кп — си+ п < < сп1яи, где последнее неравенство выполняется при с > 1. Теперь, согласно методу математической индукции, необходимо доказать, что наше решение справедливо для граничных условий. Обычно для этого достаточно показать, что граничные условия являются подходящей базой для доказательства по индукции.
В рекуррентном соотношении (4.4) необходимо доказать, что константу с можно выбрать достаточно большой для того, чтобы соотношение Т(п) < оп1я п было справедливо и для граничных условий. Такое требование иногда приводит к проблемам. Предположим, что Т (1) = 1 — единственное граничное условие рассматриваемого рекуррентного соотношения. Далее, для п = 1 соотношение Т(п) < сп1ки дает нам Т(1) < с 1 1к1 = О, что противоречит условию Т (1) = 1.
Следовательно, данный базис индукции нашего доказательства не выполняется. Часть 1. Основы Эту сложность, возникающую при доказательстве предположения индукции для указанного граничного условия, легко обойти. Например, в рекуррентном соотношении (4.4) можно воспользоваться преимуществами асимптотических обозначений, требующих доказать неравенство Т (и) < си !я и только для п > оо, где ио — выбранная нами константа. Идея по устранению возникшей проблемы заключается в том, чтобы в доказательстве по методу математической индукции не учитывать граничное условие Т(1) = 1. Обратите внимание, что при и > 3 рассматриваемое рекуррентное соотношение явным образом от Т (1) не зависит.
Таким образом, выбрав по = 2, в качестве базы индукции можно рассматривать не Т(1), а Т (2) и Т (3). Заметим, что здесь делается различие между базой рекуррентного соотношения (и = 1) и базой индукции (и = 2 и п = 3). Из рекуррентного соотношения следует, что Т (2) = 4, а Т (3) = 5. Теперь доказательство по методу математической индукции соотношения и < сп 1я п для некоторой константы с > 1 можно завершить, выбрав ее достаточно большой для того, чтобы были справедливы неравенства Т (2) < 2с1к 2 и Т (3) < Зс1я 3. Оказывается, что для этого достаточно выбрать с > 2.
В большинстве рекуррентных соотношений, которые нам предстоит рассмотреть, легко расширить граничные условия таким образом, чтобы предположение индукции оказалось верным для малых и. Как угадать решение К сожалению, не существует общего способа, позволяющего угадать правильное решение рекуррентного соотношения. Для этого требуется опыт, удача и творческое мышление.
К счастью, существуют определенные эвристические приемы, которые могут помочь сделать правильную догадку. Кроме того, для получения предполагаемого вида решения можно воспользоваться деревьями рекурсии, с которыми мы ознакомимся в разделе 4.2. Если рекуррентное соотношение подобно тому, которое мы только что рассматривали, то разумно предположить, что решения этих соотношений будут похожими. Например, рассмотрим рекуррентное соотношение Т (и) = 2Т (1и/2) + 17) + п, которое выглядит более сложным, поскольку в аргументе функции Т в его правой части добавлено слагаемое "17". Однако интуитивно понятно, что это дополнительное слагаемое не может сильно повлиять на асимптотическое поведение решения. При достаточно больших и разность между Т ( 1п/21 ) и Т ( 1п/21' + 17) становится несущественной: оба эти числа приблизительно равны половине числа и. Следовательно, можно предположить„что Т (и) = О (и1яп), и проверить это с помощью метода подстановки (упражнение 4.1-5).
Другой способ найти решение — сделать грубую оценку его верхней и нижней границ, а затем уменьшить неопределенность до минимума. Например, в рекур- Глава 4. Рекуррентные соотношения рентном соотношении (4.4) в качестве начальной нижней границы можно было бы выбрать Т (п) = П (и), поскольку в нем содержится слагаемое и; можно также доказать, что грубой верхней границей является Т (и) = О (пз).
Далее верхняя граница постепенно понижается, а нижняя — повышается до тех пор, пока не будет получено правильное асимптотическое поведение решения Т (и) = 9 (и 1й и). Тонкие нюансы Иногда бывает так, что можно сделать правильное предположение об асимптотическом поведении решения рекуррентного соотношения, но при этом возникают трудности, связанные с выполнением доказательства по методу математической индукции. Обычно проблема заключается в том, что выбрано недостаточно сильное предположение индукции, которое не позволяет провести подробное рассмотрение. Натолкнувшись на такое препятствие, пересмотрите предположение индукции, избавившись от членов низшего порядка.
При этом часто удается провести строгое математическое доказательство. Рассмотрим рекуррентное соотношение: Т(п) = Т(1п/21')+ Т(~п/2))+ 1. Можно предположить, что его решение — О (и). Попытаемся показать, что для правильно выбранной константы с выполняется неравенство Т (и) < сп. Подставив предполагаемое решение в рекуррентное соотношение, получим выражение Т (и) < с ~п/2) + с (и/21 + 1 = оп + 1, из которого не следует Т (и) < сп ни для какого с. Можно попытаться сделать другие предположения, например, что решение — Т(п) = О (пз), но на самом деле правильным является именно наше первоначальное предположение. Однако чтобы это показать, необходимо выбрать более сильное предположение индукции.
Интуитивно понятно, что наша догадка была почти правильной: мы ошиблись всего лишь на константу, равную 1, т.е. на величину низшего поралка. Тем не менее, математическая индукция не работает, если в предположении индукции допущена даже такая, казалось бы, незначительная ошибка. Эту трудность можно преодолеть, если вычесть в первоначальном предположении слагаемое низшего порядка. Таким образом, теперь предположение индукции имеет вид Т (и) < сп— — Ь, где Ь > Π— константа. Теперь мы имеем следующее соотношение: Т(п) < (с ~п/2) — Ь)+ (с (и/2) — Ь) + 1 = = сп — 2Ь+1 < сп — Ь, которое справедливо при Ь > 1. Как и раньше, чтобы выполнялись граничные условия, константу с необходимо выбрать достаточно большой.
Часть 1. Основы 114 Большинство считает прием, при котором вычитаются слагаемые низшего порядка, трудным для понимания. Однако что же остается делать, когда математика не работает, если не усилить предположение? Чтобы понять этот шаг, важно помнить, что мы используем математическую индукцию: более сильное утверждение для данного фиксированного значения можно доказать, лишь предположив истинность более сильного утверждения для меньших значений.
Остерегайтесь ошибок Используя асимптотические обозначения, легко допустить ошибку. Например, для рекурреитного соотношения легко "доказать", что Т (и) = 0 (и), предположив справедливость соотношения Т (и) < сп, а затем выписав цепочку соотношений Т(п) < 2(с(п/2)) + и < си+ и = = О (п), — не верно!!! поскольку с — константа. Ошибка заключается в том, что не была доказана гипо- теза индукции в точном виде„т.е. в виде Т (и) < сп.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
