Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 25
Текст из файла (страница 25)
4.6. Дерево рекурсии лия рекурренгного соотношения Т(и) = Т(и/3) -(- Т(2и/3) -(- сл. Давайте теперь рассмотрим более сложный пример. На рис. 4.6 представлено дерево рекурсии для рекуррентного соотношения Т(п) = Т(п/3) + Т(2п/3) + 0(п) . (Здесь также для простоты опущены функции "пол" и "потолок".) Пусть с, как и ранее, представляет постоянный мнояситель в члене 0(п). При суммировании величин по всем узлам дерева, принадлежащим определенному уровню, для каждого уровня мы получаем величину сп.
Самый длинный путь от корня дерева до его листа имеет вид п -+ (2/3)п — + (2/3)2п — ~ . -+ 1. Поскольку (2/3)ьп = 1 при )с = 1окз/2 и, высота дерева равна 1окз/2 п. Интуитивно мы ожидаем, что решение рекуррентного соотношения не превосходит количества уровней, умноженного на стоимость каждого уровня, или 0(сп!ойз/2 и) = 0(п)кп).
На рис.4.6 показаны только верхние уровни дерева рекурсии, и не каждый уровень дерева дает вклад сп. Рассмотрим стоимость листьев, Если это дерево рекурсии представляет собой полное бинарное дерево высотой 1окз/2 и, в нем должно иметься 2(окм'" = п~'квг' листьев. Поскольку стоимость каждого листа является константой, общая стоимость листьев должна составлять сэ(п~'ивг' ), что является ог(п 1я п), поскольку 1ояз/ 2 представляет собой константу, строго большую, чем 1. Однако это дерево рекурсии не являЕтея ПОЛНЫМ бИНарНЫМ дЕрЕВОМ, а ПОтОМу ИМЕЕТ МЕНЕЕ П(оав1'2 ЛИСТЬЕВ.
БОЛЕЕ того, по мере удаления от корня отсутствует все большее количество внутренних узлов. Следовательно, не для всех уровней время их работы выражается как сп; более низкие уровни дают меньший вклад. Можно было бы попытаться аккуратно учесть вклады всех элементов дерева, однако вспомним, что мы всего лишь угш(ываем вид решения, чтобы затем воспользоваться методом подстановок. Давайте отклонимся от точного решения и допустим, что асимптотическая верхняя граница решения представляет собой 0(п 1я п). Действительно, можно использовать метод подстановок, чтобы проверить, что 0(п)кп) является верхней границей решения рекуррентного соотношения.
Покажем, что Т(п) ( с)п1я п, где (1 — подходящая положительная константа. Мы чаавь т Основы имеем Т(п) < Т(п/3) + Т(2п/3) + сп < с~(п/3) 1к(п/3) + Ы(2п/3) 1к(2п/3) + сп = (сХ(п/3) 13 и — сК(п/3) 1к 3) + (сХ(2п/3) 1к и — Н(2п/3) 1к(3/2)) + сп = дп 13 и — И((п/3) 1к 3 + (2п/3) 1к(З/2)) + сп = Ып 1к и — Ы((п/3) 1к 3 + (2п/3) 1к 3 — (2п/3) 1к 2) + сп = Нп1ка — дп(1кЗ вЂ” 2/3) + сп < йп1яп при Ы > с/(!й 3 — (2/3)). Таким образом, нам не нужно выполнять более точный учет стоимости в дереве рекурсии.
Упражнения 4.4.1 Воспользуйтесь деревом рекурсии для определения точной асимптотической верхней границы рекуррентного соотношения Т(п) = ЗТ((п/2)) + и. Для проверки своего ответа используйте метод подстановок. 4.4.2 Воспользуйтесь деревом рекурсии для определения точной асимптотической верхней границы рекуррентного соотношения Т(п) = Т(п/2) + па. Для проверки своего ответа используйте метод подстановок. 4.4.5 Воспользуйтесь деревом рекурсии для определения точной асимптотической верхней границы рекуррентного соотношения Т(п) = 4Т(п/2+ 2) + п.
Для проверки своего ответа используйте метод подстановок. 4.4.4 Воспользуйтесь деревом рекурсии для определения точной асимптотической верхней границы рекуррентного соотношения Т(п) = 2Т(п — 1) + 1. Для проверки своего ответа используйте метод подстановок. 4.4.5 Воспользуйтесь деревом рекурсии для определения точной асимптотической верхней границы рекуррентного соотношения Т(п) = Т(п — 1) + Т(п/2) + п. Для проверки своего ответа используйте метод подстановок.
4.4.6 Обратившись к соответствующему дереву рекурсии, докажите, что решением рекуррентного соотношения Т(п) = Т(п/3) + Т(2п/3) + сп, где с представляет собой константу, является Й(п 13 и). Глава 4. Разделяй ы властвуй !з:9 4.4. 7 Постройте дерево рекурсии для рекуррентного соотношения Т(п) = 4Т( (и/2) ) + сп, где с — константа, и найдите точную асимптогическую границу его решения. Проверьте ее с помощью метода подстановок.
4.4.8 Найдите с помощью дерева рекурсии точную асимптотическую оценку решения рекуррентного соотношения Т(п) = Т(п — а) + Т(а) + сп„где а > 1 и с > 0 являются константами. 4.4.9 Найдите с помощью дерева рекурсии точную асимптотическую оценку решения рекуррентного соотношения Т(п) = Т(ап) + Т((1 — а)п) + сп, где а — константа из диапазона 0 < а < 1; константой является и с > О.
4.5. Основной метод Основной метод является своего рода "кулинарной книгой", по которой строятся решения рекуррентных соотношений вида Т(п) = аТ(п/Ь) + /(и), (4.20) где а > 1 и 6 > 1 — константы, а У(п) — асимптотически положительная функция. Чтобы научиться пользоваться этим методом, необходимо запомнить три случая, что значительно облегчает решение многих рекуррентных соотношений, а часто это можно сделать даже в уме. Рекуррентное соотношение (4.20) описывает время работы алгоритма, в котором задача размером и разбивается на а вспомогательных задач размером и/6 каждая, где а и 6 — положительные константы.
Полученные в результате разбиения а подзадач решаются рекурсивно, причем время решения каждой из ннх равно Т(п/Ь). Время, требуемое для разбиения задачи и объединения результатов, полученных при решении вспомогательных задач, описывается функцией /(и). Например, в рекуррентном соотношении, возникающем в ходе анализа алгоритма Штрассена, а = 7, Ь = 2, а У(п) = Н(пз). Строго говоря, при определении приведенного выше рекуррентного соотношения допущена неточность, поскольку число и/Ь может не быть целым. Однако замена каждого из а слагаемых Т(п/Ь) выражением Т((п/6)) или Т((п/6)) не влияет на асимптотическое поведение решения (это будет доказано в следующем разделе). Поэтому обычно при составлении рекуррентных соотношений подобного вида, полученных методом "разделяй н властвуй", мы будем игнорировать функции "пол'" и "потолок". Основная теорема Основной метод зависит от следующей теоремы. Часть Ь Основы 12О Теорема 4.1 (основная теорема) Пусть а > 1 и Ь > 1 — константы, /(п) — функция, а Т(п) определена на множестве неотрицательных целых чисел с помощью рекуррентного соотношения Т(п) = аТ(и/Ь) + /(п), где и/Ь интерпретируется либо как 1иЯ, либо как (п/Ь) .
Тогда Т(п) имеет следующие асимптотические границы. 1. Если /(п) = 0(пыаь' ') для некоторой константы е > О, то Т(п) = В(п~оаь'). 2. Если /(п) = 9(пгок"), то Т(п) = 6(пмаьо 1яп). 3. Если /(п) = П(и~окно+') для некоторой константы е > 0 и если а/(п/Ь) < с/(и) для некоторой константы с < 1 и всех достаточно больших п, то Т(п) = В(/( )). Прежде чем применить основную теорему к некоторым конкретным примерам, потратим немного времени на понимание ее сути.
В каждом из трех случаев функция /(п) сравнивается с функцией и'а" '. Интуитивно понятно, что большая из этих двух функций определяет решение рекуррентного соотношения. Если, как в случае 1, функция п'яь о больше, то решение имеет вид Т(п) = 9(пгоаь'). Если, как в случае 3, большей является функция /(и), то решение представляет собой Т(п) = 6(/(п)). Если же, как в случае 2, две эти функции сравнимы, мы выполняем умножение на логарифмический множитель, и решением является Т(п) = Й(п"аь ' 1к п) = 9(/(п) 1я п). Помимо интуитивных представлений, нужно знать и некоторые технические детали.
В первом случае функция /(п) должна быть не просто меньше, чем и"а", а нолиномиально меньше (т.е. /(и) должна быть асимптотически меньше пмкь' на множитель и' для некоторой константы е > О). В третьем случае функция /(и) должна быть не просто больше и"аь', но полиномиально больше, и к тому же удовлетворять условию "регулярности" а/(п/Ь) < с)(п).
Это условие удовлетворяется большинством полиномиально ограниченных функций, с которыми нам предстоит встречаться, Важно понимать, что этими тремя случаями не исчерпываются все возможности поведения функции /(и). Между случаями 1 и 2 есть промежуток, в котором функция /(п) меньше функции п'а", но не полиномиально меньше. Аналогичный промежуток имеется между случаями 2 и 3, когда функция /(п) больше функции п"аь', но не полиномиально больше.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
