Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 24
Текст из файла (страница 24)
Нам надо показать, что для некоторой константы !!' > 0 выполняется неравенство Т (и) < огР. Используя ту же константу с > О, что и раньше, получаем: Т (и) < ЗТ (~п/4) ) + сп~ < 311 ~ и/4) ~ + сп~ < 3 Гб < 311(п/4) + стР = — г1пз+ сгР < !ЬР, где последнее неравенство выполняется при !з' > (16/13) с. Глава 4. Рекуррентные соотношения 119 сл Вл. сл / ~ / с(4) с(г) с(г) с(г) ------~ сл Всего: 0(л)ал) Рис.
4.2. Дерево рекурсии, соответствующее рекуррснтному соотношению Т (п) = Т (и/3) + Т (2п/3) + сп Давайте теперь рассмотрим более сложный пример. На рис. 4.2 представлено дерево рекурсии для рекуррентного соотношения: Т (п) = Т (и/3) + Т (2п/3) + сп. (Здесь также для простоты опущены функции "пол" и "потолок".) Пусть с, как и раньше, представляет постоянный множитель в члене О (п). При суммировании величин по всем узлам дерева, принадлежащим определенному уровню, для каждого уровня мы получаем величину сп.
Самый длинный путь от корня дерева до его листа имеет вид и — (2/3) п -л (2/3) п -л... -г 1. Из (2/3) п = 1 следует, что высота дерева равна 1окз/з и. Интуитивно понятно, что асимптотическое поведение предполагаемого решения рекуррентного соотношения определяется произведением количества уровней на время выполнения каждого уровня, т.е. О (сп 1окз/з и) = О (п 1к и). В данном случае время выполнения равномерно распределяется по всем уровням дерева рекурсии. Здесь возникает одна сложность: нужно определить время работы каждого листа. Если бы рассматриваемое дерево рекурсии было полностью бинарным с высотой 1окз/зп, то всего имелось бы 2) Ялгл" = п~~клг' листьев. Поскольку время выполнения каждого листа выражается константой, сумма этих констант по всем листьям была бы равна сг (пкжлгл з), т.е. ог (и 1к и). На самом деле это дерево рекурсии нельзя назвать полностью бинарным, поэтому у него меньше, чем п 'алг' листьев.
Более того, по мере удаления от корня отсутствует все большее количество внутренних узлов. Следовательно, не для всех уровней время их работы выражается как сп; более низкие уровни дают меньший вклад. Можно было бы попытаться аккуратно учесть вклады всех элементов дерева, однако вспомним, что мы всего лишь угадываем вид решения, чтобы затем воспользоваться Часть !. Основы 120 методом подстановок. Давайте отклонимся от точного решения и допустим, что асимптотическая верхняя граница решения ведет себя как О (и !я п). С помощью метода подстановок мы можем убедиться, что сделанное выше предположение корректно.
Покажем, что при подходящем выборе положительной константы д выполняется неравенство Т (и) < Мп 1кп. Можно записать цепочку соотношений: Т(п) < Т(п/3) +Т(2п/3) + сп < < а1 (и/3) 1к (и/3) + д (2п/3) 1к (2п/3) + сп = = (сР (п/3) 1я и — д (и/3) !к 3) + (Н (2п/3) 1я и — сЮ (2п/3) 1к (3/2) ) + сп = = Йп13п — д((п/3) 1к3+ (2п/3) 1к(3/2)) + сп = = г1п!я п — гХ ((и/3) !я 3 + (2п/3) 1б 3 — (2п/3) 1я 2) + сп = = а!и 1й п — сй~ (!я 3 — 2/3) + сп < < дп1кп, которые выполняются при й > с/(!й3 — (2/3)) .
Таким образом, решение не делать более точный учет времени работы элементов, из которых состоит дерево рекурсии, вполне оправдало себя. Упражнения 4.2- 1. Определите с помощью дерева рекурсии асимптотическую верхнюю границу рекуррентного соотношения Т(п) = 3Т(1п/2)) + и. Проверьте ответ методом подстановок.
4.2-2. Обратившись к дереву рекурсии, докажите, что решение рекуррентного соотношения Т (и) = Т (и/3) + Т (2п/3) + сп, где с — константа, ведет себя как П (и 1я п). 4.2-3. Постройте дерево рекурсии для рекуррентного соотношения Т(п) = = 4Т ( 1п/2) )+сп, где с — константа, и найдите точную асимптотическую границу его решения. Проверьте ее с помощью метода подстановок. 4.2-4. Найдите с помощью дерева рекурсии точную асимптотическую оценку решения рекуррентного соотношения Т (и) = Т (и — а) + Т (а) + сп, где а > 1 и с > Π— константы. 4.2-5. Найдите с помощью дерева рекурсии точную асимптотическую оценку решения рекуррентного соотношения Т (и) = Т (оп)+Т ((1 — а) и)+си, где О < о < 1 и с > Π— константы.
Глава 4. Рекуррентные соотношения 4.3 Основной метод Основной метод является своего рода "сборником рецептов", по которым строятся решения рекуррентных соотношений вида Т (и) = аТ (и/Ь) + / (и), (4. 5) где а > 1 и Ь > 1 — константы, а / (и) — асимптотически положительная функция. Чтобы научиться пользоваться этим методом, необходимо запомнить три случая, что значительно облегчает решение многих рекуррентных соотношений, а часто это можно сделать даже в уме.
Рекуррентное соотношение (4.5) описывает время работы алгоритма, в котором задача размером и разбивается на а вспомогательных задач, размером и/Ь каждая, где а и Ь вЂ” положительные константы. Полученные в резуль~тте разбиения а подзадач решаются рекурсивным методом„причем время их решения равно Т (и/Ь).
Время, требуемое для разбиения задачи и объединения результатов, полученных при решении вспомогательных задач, описывается функцией /(и). Например, в рекуррентном соотношении, возникающем при анализе процедуры Миксе Яокт, а = 2, Ь = 2, а /(и) = 6 (и). Строго говоря, при определении приведенного выше рекуррентного соотношения допущена неточность, поскольку число п/Ь может не быть целым. Однако замена каждого из а слагаемых Т (и/Ь) выражением Т ('1п/Ь)) или Т ((и/Ь1 ) не влияет на асимптотическое поведение решения (это будет доказано в следующем разделе). Поэтому обычно при составлении рекуррентных соотношений подобного вида, полученных методом "разделяй и властвуй", обычно мы будем игнорировать функции "пол" и "потолок", с помощью которых аргумент преобразуется к целому числу. Основная теорема Основной метод базируется на приведенной ниже теореме.
теорема 4.1 (Основная теорема). Пусть а > 1 и Ь > 1 — константы, /(и)— произвольная функция, а Т (и) — функция, определенная на множестве неотрицательных целых чисел с помо|цью рекуррентного соотношения Т(п) = аТ(п/Ь)+ /(и), где выражение и/Ь интерпретируется либо как 1п/Ь), либо как (п/Ь1.
Тогда асимптотическое поведение функции Т (и) можно выразить следующим образом. 1. Если Яп) = О (пмк~' ') для некоторой константы е > О, то Т(п) = — О (пми ) Часть!. Основы 122 2. Если / (и) = 6 (пык~'), то Т (и) = 9 (пыхал а 1к и). 3. Если /(и) = й(пмво'+') для некоторой константы е ) О, и если а/ (и/Ь) < с/ (и) для некоторой константы с < 1 и всех достаточно больших и, то Т (и) = О (/ (и)). 13 Перед тем как применение основной теоремы будет продемонстрировано на конкретных примерах, попытаемся понять ее суть. В каждом из трех выделенных в теореме случаев функция /(и) сравнивается с функцией и'я~~. Интуитивно понятно, что асимптотическое поведение решения рекуррентного соотношения определяется большей из двух функций.
Если большей является функция и "Я '*, как в случае 1, то решение — Т (и) = О (п1'Я~ ) . Если быстрее возрастает функция / (и), как в случае 3, то решение — Т (и) = О (/ (и)). Если же обе функции сравнимы, как в случае 2, то происходит умножение на логарифмический множитель и решение — Т(п) = О (пык~ 1кп) = О(/(и) 1кп). Кроме этих интуитивных рассуждений, необходимо разобраться с некоторыми техническими деталями. В первом случае функция / (и) должна быть не просто меньше функции пп'Яь ', а нолиномиально меньше.
Это означает, что функция / (и) должна быть асимптотически меньше функции и"'к~ в и' раз, где е — неюторая положительная константа. Аналогично, в третьем случае функция /(и) должна быть не просто больше функции и'Яь ', а полиномиально больше, и, кроме того, удовлетворять условию "регулярности**, согласно которому а/ (и/Ь) < с/ (и). Это условие выполняется для большинства полиномиально ограниченных функций, с которыми мы будем иметь дело. Важно понимать„что этими тремя случаями не исчерпываются все возможности поведения функции / (и). Между случаями 1 и 2 есть промежуток, в ютором функция У (и) меньше функции п~"Я~', но не полиномиально меньше.
Аналогичный промежуток имеется между случаями 2 и 3, когда функция / (и) больше функции п~~к~~, но не полиномиально больше. Если функция /(и) попадает в один из этих промежутков, или если для нее не выполняется условие регулярности из случая 3, основной метод неприменим для решения рекуррентных соотношений.
Использованне основного метода Чтобы использовать основной метод, достаточно определить, какой из частных случаев основной теоремы (если такой есть) применим в конкретной задаче, а затем записать ответ. В качестве первого примера рассмотрим такое рекуррентное соотношение: Т(п) = 9Т(п/3) + и. В этом случае а = 9, Ь = 3, / (и) = и, так что пмкз" = пп'и в = 9 (п~). Поскольку /(и) = О (пмкзэ '), где е = 1, можно применить случай 1 основной теоремы и сделать вывод, что решение — Т (п) = О (пз). Глава 4.
Рекуррентные соотношения 123 Теперь рассмотрим следующее рекуррентное соотношение: Т (п) = Т (2п/3) + 1, в котором а = 1, Ь = 3/2, /(п) = 1, а пп~а1~ = п~ам' = п = 1. Здесь применим случай 2, поскольку / (п) = О (п'Я~") = О (1), поэтому решение— Т (п) = О (1к п). Для рекуррентного соотношения Т(п) = 3Т(п/4) + п1кп выполняются условия а = 3, Ь = 4, / (п) = п 1я и, н пмаь а = пма4 з = О (пател).
Поскольку / (п) = й (п"Я4 з+'), где е - 0.2, применяется случай 3 (еслн удастся показать выполнение условия регулярности для функции / (п)). При достаточно больших и условие а/ (и/Ь) = 3 (и/4) 1к (и/4) < (3/4) и 1й и = с/ (и) выполняется при с = 3/4. Следовательно, согласно случаю 3, решение этого рекуррентного соотношения — Т (п) = О (п 1я и).
К рекуррентному соотношению Т(п) = 2Т(п/2) + п1йп основной метод неприменим, несмотря на то, что оно имеет надлежащий вид: а = 2, Ь = 2, / (п) = п 1к п, и п'Яь ' = п. Может показаться, что к нему применим случай 3, поскольку функция / (п) = п 1к п асимптотически больше, чем п'~~ ' = = п. Однако проблема заключается в том, что данная функция не лолиномиально больше. Отношение /(п)/пма~ = (п1кп)/и = 1яп асимптотически меньше функции па для любой положительной константы е. Следовательно, рассматриваемое рекуррентное соотношение находится "в промежуточном состоянии'* между случаями 2 и 3. (См.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
