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