Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 26
Текст из файла (страница 26)
Если функция /(п) попадает в один из этих промежутков или если для нее не выполняется условие регулярности из случая 3, для решения таких рекуррентных соотношений основной метод неприменим. Использование основного метода При использовании основного метода мы просто определяем, какой из случаев основной теоремы (если таковой имеет место) применим в данной ситуации, и записываем ответ. Глава а Разделяй и властвуй В качестве первого примера рассмотрим Т(п) = 9Т(п/3) + и .
В этом рекуррентном соотношении мы имеем а = 9, Ь = 3, /(и) = и, так что п1оаза п!оказ ез(пз) Поскольку /(и) = О(п1окз9 — ~) зде е = 1 мы мох(ем применить случай 1 основной теоремы и сделать вывод, что решение имеет внд Т(п) = Э(п ). Рассмотрим теперь рекуррентное соотношение Т(п) = Т(2п/3) + 1, в мзтором а = 1, Ь = 3/2, /(и) = 1 и п1акз' = п~ааз!з = пс = 1. Здесь применим случай 2, поскольку /(и) = 1В(п"аз') = б1(1), и, таким образом, решение рекуррентного соотношения представляет собой Т(п) = 1В(!я и). В случае рекуррентного соотношения Т(п) = ЗТ(и/4) + п1кп мы имеем а = 3, 6 = 4, /(и) = п1йп и и"ква = п~ = 0(по™з).
Поскольку /(и) = П(п"кл з+'), где в = 0.2, можно применить случай 3, если мы сможем показать, что для функции /(и) выполняется условие регулярности. При достаточно больших п мы получаем, что а/(и/6) = 3(п/4) 1я(п/4) < (3/4)п !к п = с/(и) для с = 3/4. Следовательно, в соответствии со случаем 3 решением рекуррентного соотношения является Т(п) = б1(п 1к и). Основной метод неприменим к рекуррентному соотношению Т(п) = 2Т(п/2) + и !яп несмотря на то, что оно выглядит как имеющее корректный вид: а = 2, Ь = 2, /(и) = п!яп и и"кз' = п.
Вы можете ошибочно решить, что к нему применим случай 3, поскольку /(и) = п!яп асимптотически больше, чем пмава = и. Проблема в том, что данная функция больше не лалкнамиальио. Отношение дп)/п1акз' = (п1яп)/и = !к п асимптотически меньше и' для любой положительной константы в. Таким образом, рассматриваемое рекуррентное соотношение попадает в "зазор" между случаями 2 и 3.
(См. решение этого рекуррентного соотношения в упр. 4.6.2.) Применим основной метод к решению рекуррентных соотношений, с которыми мы встречались в разделах 4.1 и 4.2. Рекуррентное соотношение (4.7), Т(п) = 2Т(п/2) + 9(п), характеризует время работы алгоритмов "разделяй и властвуй" для задачи поиска максимального подмассива и сортировки слиянием. (Как обычно для практических целей, мы опускаем базовый случай рекуррентного соотношения.) Здесь мы имеем а = 2, Ь = 2, /(и) = б1(п) и, таким образом, получаем, что и'аз' = Часть Х Основы и'"а2 з = п. Применим случай 2, поскольку Дп) = 9(п), так что решением рекуррентного соотношения является Т(п) = ез(п 18 и). Рекуррентное соотношение (4.
17), Т(п) = ВТ(п/2) + 9(пз), описывает время работы первого алгоритма "разделяй и властвуй" для матричного умножения. Мы имеем а = 8, Ь = 2 и /(п) = 9(пз), так что п~ аь' = имя2а = пз. Поскольку пз полиномиально больше Ди) (т.е. Дп) = 0(пз ') для с = 1), применим случай 1, и Т(п) = Й(пз). Наконец рассмотрим рекуррентное соотношение (4.18), Т(п) = 7Т(и/2) + 9(п ), которое описывает время работы алгоритма Штрассена.
В этом случае а = 7, 6 = 2, Дп) = 6(пз), так что имкь = пьвь ~. Переписав 1оВз 7 как 187 и вспомнив, что 2.80 < 1В 7 < 2.81, мы видим, что /(п) = 0(п'ат ') для е = 0.8. Вновь можно применить случай 1 и получить решение Т(п) = 9(и'а т). Упражнения 4.5.1 С помощью основной теоремы найдите точные асимптотические границы следу- ющих рекуррентных соотношений. ж Т(и) = 2Т(п/4)+ 1. б. Т(п) = 2Т(п/4) + ь/й.
в, Т(п) = 2Т(п/4) + и, г. Т(п) = 2Т(п/4) + пз. 4.5.2 Профессор хочет разработать алгоритм матричного умножения, асимптотически более быстрый, чем алгоритм Штрассена. Его алгоритм будет использовать метод "разделяй и властвуй", разбивая каждую матрицу на части размером и/4 х и/4, причем шаги разделения и комбинирования выполняются за время 6(пз). Профессору требуется определить, сколько подзадач должен создавать его алгоритм, чтобы опередить алгоритм Штрассена. Если алгоритм профессора создает а подзадач, то рекуррентное соотношение для времени работы Т(и) принимает вид Т(и) = аТ(и/4) + 9(пз). Каково наибольшее целочисленное значение а, для которого алгоритм профессора оказывается асимптотически быстрее алгоритма Штрассена? 4.5.3 Покажите с помощью основного метода, что Т(п) = 9(18 и) является решением рекуррентного соотношения Т(п) = Т(п/2)+ еэ(1), возникающего в ходе анализа алгоритма бинарного поиска.
(Алгоритм бинарного поиска описан в упр. 2.3.5.) Глава 4. Разделяй и власий 4.5.4 Можно ли применить основной метод к рекурреитному соотношению Т(п) 4Т(п/2) + из)8п? Обоснуйте свой ответ. Найдите асимптотическую верхнюю границу решения этого рекуррентного соотношения. 4.5.5 * Рассмотрим условие регулярности а5(п(Ь) < с5(п) для некоторой константы с < 1, являющееся частью случая 3 основной теоремы.
Приведите примеры констант а > 1 и 6 > 1 и функции 5'(и), которые удовлетворяют всем условиям случая 3 основной теоремы, кроме условия регулярности. * 4.6. Доказательство основной теоремы В этом разделе содержится доказательство основной теоремы (теоремы 4.1). Для применения самой теоремы понимать доказательство необязательно. Доказательство состоит из двух частей. В первой части анализируется "основное" рекуррентное соотношение (4.20) с учетом упрощающего предположения, согласно которому Т(п) определена только для точных степеней числа Ь > 1, т.е. для и = 1,6,6з,....
В этой части представлены все основные идеи, необходимые для доказательства основной теоремы. Во второй части доказательство обобщается на множество всех натуральных и; кроме того, здесь при доказательстве применяются все необходимые для решения проблемы с полами и потолками математические методы. В данном разделе асимптотические обозначения будут несколько видоизменены: с их помощью будет описываться поведение функций, определенных только для целых степеней числа Ь, хотя согласно определению асимптотических обозначений неравенства должны доказываться для всех достаточно больших чисел, а не толью для степеней числа Ь.
Поскольку можно ввести новые асимптотические обозначения, применимые к множеству чисел (6':1= 0,1,2,...), а не ко всему множеству неотрицательных целых чисел, упомянутое видоизменение несущественно. Тем не менее, применяя асимптотические обозначения на суженной области определения, необходимо быть внимательным, чтобы не прийти к неверным выводам. Например, если доказано, что Т(п) = 0(п), если и — степень двойки, то это еще не означает, что Т(п) = 0(п) для всех и. Функция Т(п) может быть определена так. п , если и = 1,2,4,8,..., и в противном случае . В этом случае наилучшей верхней границей, как легко доказать, является Т(п) = 0(пз).
Во избежание подобных ошибок мы никогда не будем использовать асимптотические обозначения на ограниченной области определения функции, если только из контекста не будет вполне очевидно, что именно мы собираемся делать. Часть!. Основы 4.б.1. Доказательство теоремы для точных степеней В первой части доказательства основной теоремы анализируется рекуррентное соотношение (4.20), Т(п) = аТ(п/Ь) + /(и), в предположении, что п — точная степень числа 6 > 1, где Ь вЂ” необязательно целое число.
Анализ проводится путем доказательства трех лемм. В первой из них решение основного рекуррентного соотношения сводится к вычислению выражения, содержащего суммирование. Во второй лемме определяются границы этой суммы. В третьей лемме с помощью первых двух доказывается версия основной теоремы для случая, когда и — точная степень 6. Лемма 4.3 Пусть а > 1 и Ь > 1 — константы, а /(п) — неотрицательная функция, определенная для точных степеней числа 6.
Определим функцию Т(п) на множестве точных степеней числа 6 с помощью рекуррентного соотношения Т ()= если и = 1, Т(п) = аТ(и/Ь) + /(п), если п = Ь', где 1 — положительное целое число. Тогда 1ояь н — 1 Т(и) а1(пьояь а) ! Х~Ь аа/(П/ЬЬ) (4.21) Доказаяьельсявеа. Воспользуемся деревом рекурсии, представленным на рис. 4Л, Корень дерева имеет стоимость /(п), и у него а дочерних ветвей, стоимость каждой из которых равна /(и/Ь). (В ходе этих рассуждений, особенно для визуального представления дерева рекурсии, удобно считать число а целым, хотя это и не следует из каких-либо математических соотношений.) Каждая из этих дочерних ветвей, в свою очередь, также имеет а дочерних ветвей (таким образом, получается, что на втором уровне дерева имеется а узлов), время выполнения каждой из которых равно /(п/Ьз).
Обобщая эти рассуждения, можно сказать, что на 1-м уровне находится аэ узлов, стоимость каждого из которых равна /(п/Ьь). Стоимость каждого листа равна Т(1) = йэ(1), и все листья находятся на глубине !окьп, поскольку п/61'я " = 1, Всего же у дерева а1'яь" = пп'~ь ' листьев. Уравнение (4.21) можно получить„просуммировав стоимости всех листьев дерева, как показано на рисунке. Стоимость всех внутренних узлов уровня 1 равна ат/(п/Ь'), так что полная стоимость всех внутренних узлов составляет 1ояь н — 1 Глава 4. Рлзйвляй и властвуй !25 Г ° /(п) /(п)- Ди/Ь) /(и/Ь) /(и/Ь) »- -» - -- в а/(и/Ь) +, /(п/Ьз) Дп/Ьз) /(и/Ьз) "- и ° аз/(п/Ьз) Да Да Да /(п/Ь') Ди/Ь') -/(и/Ьз) /(и/Ьз) /(п/ЬЗ)" /(п/Гв) Да Да Да Да Да Да в(ц н(ц в(ц е(ц е(ц е(ц в(ц е(ц е(ц и(ц ...
в(ц е(ц н(ц -и- е( ы ь ) пьв, > вь"-~ Всепс В(п~'и ) ь к2 аз/(п/Ы) Рис. 4Л. Дерево рекурсии, генерируемое соотнолзеннем Т(п) = оТ(п/Ь) -ь /(и). Зто дерево представляет собой полное о-арное дерево с п"в" листьями и высотой 1ояь п. Стоимость узлов на каждой глубине показана справа, а ик сумма выражается уравнением (4.2 Ц. В алгоритме "разделяй и властвуй", лежащем в основе анализируемого рекуррентного соотношения, эта сумма соответствует стоимости разделения поставленной задачи на вспомогательные подзадачи, и последующему объединению их решений. Стоимость всех листьев, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
