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

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

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

упражнение 4.4-2.) Упражнения 4.3-1. С помощью основной теоремы найдите точные асимптотические границы следующих рекуррентных соотношений. а) Т(п) = 4Т(п/2)+п. б) Т(п) = 4Т(п/2)+ п~. в) Т(п) = 4Т(п/2) + па. 4.3-2. Рекуррентное соотношение Т (п) = 7Т (и/2) + пз описывает время работы алгоритма А. Время работы альтернативного алгоритма А' выражается рекуррентным соотношением Т' (п) = аТ' (п/4) + п'.

Чему равно наибольшее целое значение а, при котором алгоритм А' работает асимптотически быстрее, чем алгоритм А. Часть 1. Основы 124 4.3-3. Покажите с помощью основного метода, что Т (и) = 9 (1яп) является решением рекуррентного соотношения Т (и) = Т (т1/2) + 6 (1), возникающего при анализе алгоритма бинарного поиска. (Алгоритм бинарного поиска описывается в упражнении 2.3-5.) 4.3-4. Можно лн применить основной метод к рекуррентному соотношению Т (и) = 4Т (и/2) + пз!к п? Обоснуйте ваш ответ.

Найдите асимптотическую верхнюю границу решения этого рекуррентного соотношения. * 4.3-5. Рассмотрим условие регулярности а/ (и/Ь) < с/ (и) для некоторой константы с < 1, являющееся частью случая 3 основной теоремы. Приведите примеры констант и > 1 н Ь > 1 и функции / (п), которые удовлетворяют всем условиям случая 3 основной теоремы, кроме условия регулярности. *4.4 Доказательство основной теоремы В этом разделе приводится доказательство основной теоремы (теорема 4.1). Для применения самой теоремы понимать доказательство необязательно.

Доказательство состоит из двух частей. В первой части анализируется "основное" рекуррентное соотношение (4.5) с учетом упрощающего предположения, согласно которому Т(и) определена только для точных степеней числа Ь > 1, т.е. для п = 1, Ь, Ьэ,.... В этой части представлены все основные идеи, необходимые для доказательства основной теоремы. Во второй части доказательство обобщается на множество всех натуральных и; кроме того, здесь при доказательстве аккуратно выполняются все необходимые округления с использованием функций "пол" и "потолок". В данном разделе асимптотические обозначения будут несколько видоизменены: с их помощью будет описываться поведение функций, определенных только для целых степеней числа Ь, хотя согласно определению асимптотических обозначений неравенства должны доказываться для всех достаточно больших чисел, а не только для степеней числа Ь.

Поскольку можно ввести новые асимптотические обозначения, применимые к множеству чисел (Ь': г = 0,1,...), а не ко всему множеству неотрицательных целых чисел, упомянутое видоизменение несущественно. Тем не менее„ применяя асимптотические обозначения на суженной области определения, необходимо быть внимательным, чтобы не прийти к неверным выводам. Например, если доказано, что Т (и) = О (п), если и — степень двойки, то это еще не означает, что Т (и) = О (и) для всех и. Функция Т (п) может быть определена так: п при п = 1,2,4,8,..., Т(п) = и для остальных значений и. Глава 4.

Рекуррентные соотношения 125 В этом случае наилучшей верхней границей, как легко доказать, является Т (и) = = О (пз). Во избежание подобных ошибок, мы никогда не будем использовать асимптотические обозначения на ограниченной области определения функции, если только из контекста не будет вполне очевидно, что именно мы собираемся делать. 4.4.1 Доказательство теоремы для точных степеней В первой части доказательства основной теоремы анализируется рекуррентное соотношение (4.5) Т(и) = аТ(п/Ь) + /(п), в предположении, что и — точная степень числа 6 > 1 16 — не обязательно целое число). Анализ производится путем доказательства трех лемм.

В первой из ннх решение основного рекуррентиого соотношения сводится к вычислению выражения, содержащего суммирование. Во второй лемме определяются границы этой суммы. В третьей лемме с помощью первых двух доказывается версия основной теоремы для случая, когда и — точная степень 6. Лемма 4.2. Пусть а > 1 и 6 > 1 — константы, а / (п) — неотрицательная функция, определенная для точных степеней числа 6. Определим функцию Т (и) на множе- стве точных степеней числа Ь с помощью такого рекуррентного соотношения: О (1) при и = 1, Т(п) = аТ (п/6) + / (п) при п = 6', где ь — положительное целое число.

Тогда получаем: Вжь "— ь Т(п) = О(пмкь ) + '~ь' аз/(п/У). (4.б) Доказашвльсоьво. Воспользуемся деревом рекурсии, представленным на рис. 4.3. Время выполнения, соответствующее корню дерева, равняется / (и). Корень имеет а дочерних ветвей, время выполнения каждой из которых равно / (и/6). (В ходе этих рассуждений, особенно для визуального представления дерева рекурсии, удобно считать число а целым, хотя это и не следует из каких либо математических соотношений.) Каждая из этих дочерних ветвей, в свою очередь, тоже имеет а дочерних ветвей, время выполнения которых равно / (и/Ьз).

Таким образом, получается, что на втором уровне дерева имеется аз узлов. Обобщая эти рассуждения,можно сказать, что на т'-м уровне находится ау узлов, а время выполнения каждого из них равно / (и/Ьь). Время выполнения каждого листа равно Т (1) = = 9 (1), и все листьЯ находЯтсЯ на глУбине 1окь и УРовнЯ, посколькУ и/Ькжь к = 1. Всего же у дерева а"кь" = и'кь" листьев. Часть 1. Основы 126 Ъ у(л) /(л)- аг(л/Ь) У(л/Ь) У(л/Ь) )оа /(и/Ьг)/(и/Ь') /(и/Ь')--- аи.

а'у(л/Ь ) Йй Й У(л/Ьги(и/Ьг) - У(и/IЬ*) Ли/Ьг)/(и/lЬ) - Лл/Ь') а а а а а а 0(1) 8(1) 8(1) 8(1) 8(1) 0(1) 0(1) 0(1) 8(1) 0(1) - 8(1) 8(1) 8(1)- ~ 8(л~') л""' Всего: 8(л""')+,"~ а'Г(л/Ь') Рис.4.3. Дерево рекурсии, генерируемое рекуррентным соотношением Т (и) = аТ /и/Ь)+ + /(и). Дерево является полным а-арным деревом высотой 1окьи с и"иеа листьями.

Время выполнения каждого уровня показано справа, а сумма этих величин выражается уравнением (4.6) Уравнение (4.6) можно получить, суммируя время выполнения всех листьев дерева, как показано на рисунке. Время выполнения внутренних узлов уровня 3 равно а// (и/Ьг), так что полное время выполнения всех внутренних узлов можно записать так: !оае л-1 аз/ (и/Ь)). /=о В алгоритмеразбиения, лежащем в основе анализируемого рекуррентного соотношения, эта сумма соответствует полному времени, затрачиваемому на разбиение поставленной задачи на вспомогательные подзадачи, и последующему объединению нх решений. Суммарное время выполнения всех листьев, т.е.

время решения всех имае' вспомогательных задач с размером 1, равно 9 (гимае ). П Три частных случая основной теоремы, выраженные в терминах дерева рекурсии, соответствуют ситуациям, когда полное время выполнения дерева 1) преимущественно определяется временем выполнения его листьев, 2) равномерно распределено по всем уровням дерева или 3) преимущественно определяется временем выполнения корня. Сумма в уравнении (4.6) описывает время, затрачиваемое на этапы разбиения и объединения в алгоритме разбиения, лежащем в основе Глава 4. Рекурреитные соотношения 127 анализируемого рекуррентного соотношения. В следующей лемме обосновыва- ются асимптотические оценки порядка роста атой суммы.

Лемма 4.3. Пусть а > 1 и Ь > 1 — константы, а / (и) — неотрицательная функция, определенная для точных степеней числа Ь. Тогда функцию д (п), определенную на множестве целых степеней числа Ь с помощью соотношения !ояь и-1 д (п) = ~~ь ау/ (п/Ьь), (4.7) можно асимптотически оценить следующим образом. 1. Если для некоторой константы е > О выполняется условие /(п) = О (п1ояь -а), то д (п) = О (п1ояь а). 2.

Если /(п) = 9 (~п~кьа), то д(п) = 9 (ппокь'1кп). 3. Если для некоторой константы с < 1 и всех п > Ь справедливо соотношение а/(п/Ь) < с/(п), тод(п) = 6(/(п)). !ояь и-1 ь11=о т..~( — ")~' '). у=о (4.8) Оценим сумму в О-обозначении. Для этого вынесем из-под знака суммирова- ния постоянный множитель и выполним некоторые упрощения, в результате чего сумма преобразуется в возрастающую геометрическую прогрессию: 1окь и — 1 = п1окьа-а (-) п ь 1ояьа-а Ьз ау у=о П1оаЬив п1оаь а-' п1ояь а — а Доказательство.

В первом случае справедливо соотношение / (п) = О (п~'яь ' '), из которого следует, что / (п/У) = О ((п/Ь1) к' ) . Подставив зто равенство в уравнение (4.7), получим следующее соотношение: Часть 1. Основы 130 а в случае 3, поскольку / (и) = П (и"Яь"')— Т (и) — ~ (имяь ~) + с1 ( г (и))— = ~(/(и)). 4.4.2 Учет округления чисел Чтобы завершить доказательство основной теоремы, необходимо обобщить проведенный ранее анализ на случай, когда рекуррентное соотношение определено не толью для точных степеней числа Ь, но и для всех целых чисел. Получить нижнюю границу для выражения Т(п) = аТ(~п/Ь1) +/(и) (4.

10) н верхнюю границу для выражения Т(п) = аТ((п/Ь)) + /(п) (4.11) 1п/Ь1, Ц'и/Ь1 /Ь1, Н'1и/Ь1 /Ь1/Ь1 Обозначим у-й элемент этой последовательности как и, где и при д' = О, ~п д/Ь1 при д' > О. 1 у (4.12) не составляет труда, поскольку в первом случае для получения нужного результата можно использовать неравенство 1п/Ь~1 > и/Ь, а во втором — неравенство '(п/Ь)' ( и/Ь.

Чтобы получить нижнюю границу рекуррентного соотношения (4.11), необходимо применить те же методы, что и при нахождении верхней границы для рекуррентного соотношения (4.10), поэтому здесь будет показан поиск толью последней. Дерево рекурсии, представленное на рис. 4.3, модифицируется и приобретает вид, показанный на рис. 4.4. По мере продвижения по дереву рекурсии вниз, мы получаем следующую рекурсивную последовательность аргументов: Глава 4.

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

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