Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 27
Текст из файла (страница 27)
стоимость решения всех нмкьв вспомогательных подзадач размером 1, равна 9(пмкь ). Лемма 4.3 Пусп. а > 1 и б > 1 являются константами и пусть /(и) представляет собой неотрицательную функцию, определенную для точных степеней б. Функция д(п), определенная для точных степеней б с помощью соотношения 1окь п — 1 д(п) = ~ аз /(и/ьз), (4.22) Три частных случая основной теоремы, выраженные в терминах дерева рекурсии, соответствуют ситуациям, когда полная стоимость дерева (1) преимущественно определяется стоимостью его листьев, (2) равномерно распределена по всем уровням дерева или (3) преимущественно определяется стоимостью корня.
Сумма в уравнении (4.21) описывает стоимость шагов разделения и иэмбинирования в алгоритме "разделяй и властвуй", лежащем в основе анализируемого рекуррентного соотношения. В следующей лемме обосновываются асимптотические оценки порядка роста этой суммы. Часть Л Основы 126 имеет следующие асимптотические границы для точных степеней (ь.
1. Если /(и) = 0(п1ок' ') для некоторой константы с ) О, то д(п) = 0(пмк"). 2. Если /(и) = В(п"кь'), то д(п) = В(п1оаьа )яп). 3. Если а/(и/6) < с/(и) для некоторой константы с ( 1 и для всех достаточно больших и, то д(п) = 9®п)). 1окь о ь1 1=о т' 1( —,",) ' ) 1=О (4.23) Оценим сумму в 0-обозначении. Для этого вынесем из-под знака суммирова- ния постоянный множитель и выполним некоторые упрощения, в результате чего сумма преобразуется в возрастающую геометрическую прогрессию: 1ояь и — 1 мяь " 1оеьо — в ~~, ( ) (ььокь о у=с 1оаь и-1 „"к"- ~~, ' (у)3 "'"" Г"'-' ') У вЂ” 1 и 31окьо в ао —.) '() У) Поскольку б и с — константы, можно переписать последнее выражение как п'к ' '0(п') = 0(п"кь").
Подставив это выражение вместо суммы в уравнение (4.23), получим д(п) О(п1жь о) тем самым доказав случай 1. Поскольку в случае 2 предполагается, что /(п) = 9(п1окь'), получаем /(и/У) = 9((п/У)'кь'). Подстановка в уравнение (4.22) приводит к 1оаь о — 1 в1 1= о ~ в Я) '*' ) 3=О (4.24) Ограничим сумму в сэ-обозначении, как в случае 1, но в этот раз геометрическую прогрессию мы не получим. Вместо этого мы обнаружим, что почти все члены Доказательство. В случае 1 мы имеем /(и) = О(пки ' '), откуда следует, что /(и/У) = 0((и/У)"ко о '). Подстановка в уравнение (4.22) дает Глава К Разделяй и влаоязвуй !27 суммы одинаковы: 1окь и-1 1оав и-1 ~ (.".) 1окь и — 1 ( ) 1окьа — П1оаь о э=о ь = гь'к' !оя п Подставив это выражение для суммы в уравнение (4.24), получаем д(п) = ез(п оа' 1окьи) = тз(п'ало оп), 1окь и — 1 д(и) = ~ азии/Ь1) з=о 1охь и-1 < ~ с-'Яп) + О(1) з=о < г'(п) ~~ь с' + О(1) з=о = У(и) ( —,' ) + О(1) = 0(1(п)), что доказывает случай 2.
Случай 3 доказывается аналогично. Поскольку 1" (п) фигурирует в определении (4.22) функции д(п) и все члены д(п) неотрицательны, можно заключить, что для точных степеней Ь справедливо соотношение д(и) = П(1(п)). Согласно нашему предположению из формулировки леммы, для некоторой константы с < 1 и всех достаточно больших и выполняется неравенство а1(и/Ь) < с((п). Переписав зто предположение как 1(п(Ь) < (с/аЩп) и выполнив у итераций, получим 1(п/Ьз) < (с(а)11(п) или, что эквивалентно, аз1(п(Ьз) < оз1(п) в предположении, что итерируемые значения достаточно велики.
Поскольку последнее (и наименьшее) такое значение равно и/Ь' ', хватит предположения о том, что и/Ьз достаточно велико. Подстановка в уравнение (4.22) и упрощение приводят к геометрической прогрессии, но в отличие от прогрессии в случае 1 в этот раз прогрессия убывающая. 0(1) используется для записи тех членов, которые не охватываются нашим предположением о том, что и достаточно велико, Часыь 1 Основы поскольку с является константой. Таким образом, можно сделать вывод, что у(п) = Й(/(п)) для точных степеней Ь.
Доказав случай 3, мы завершили доказательство леммы. Теперь можно доказать версию основной теоремы для случая, когда и представляет собой точную степень Ь. Лемма 4.4 Пусть а > 1 и Ь > 1 — константы и пусть /(и) — неотрицательная функция, определенная для точных степеней числа 6, Определим функцию Т(п) для точных степеней числа 6 с помощью рекуррентного соотношения Е 1(Ц, если п = 1, аТ(п/6) + /(п), если п = 61, где ь — положительное целое число. Тогда Т(п) имеет следующие асимптотиче- ские границы для точных степеней Ь. 1.
Если /(и) = 0(пыль' ') для некоторой константы с > О, тоТ(п) = 9(имаь'). 2, Если у(п) = 9(п1оаьо), то Т(п) = щп1оаьо1дп). 3. Если У(и) = Й(п~'аь'+') для некоторой константы с > О и если а/(п/6) ( с/(п) для некоторой константы с < 1 и всех достаточно больших и, то Т(п) = ЙЩи)). Доказавьельсиьво. С помощью асимптотических границ из леммы 4.3 оценим значение суммы (4.21) из леммы 4.2. В случае 1 имеем Т(п) — аь(п1оаь о) + О(п1оаь о) ~( 1оаьо) а в случае 2 Т(и) В(И1оаьо) + ~(И1оаво1 П) 1В( 1оаьо) ) В случае 3 Т(п) = 9(п~'а") + ЭЩп)) =~У( )) поскольку /(п) = П(п"аз о "').
4.6.2. Полы и потолки Чтобы завершить доказательство основной теоремы, необходимо обобщить проведенный ранее анализ на случай, когда рекуррентное соотношение определе- Тлела 4. Ршделлй и властвуй !29 но не только для точных степеней числа Ь, но и для всех целых чисел. Получить нижнюю границу для выражения Т(п) = аТ(~п/61 ) + /(и) (4.25) и верхнюю границу для Т(п) = оТ((п/Ь) ) + /(и) (4.26) ('и/61, Цп/61 /Ь1, т./61 /61 /Ь1, ДП) ° Ю /(П) /(п2) - --- ---еп- а/(п2) ДП2) ()аа2 и) +, +, /(пл) /(пл) -.
/(пл) -- а' а /(пл) Да Да Да /(П2) /(П2) "' /(П2) /(П2) НП2) '" /(П2) Да Да Да Да Да Д В(Ц В(Ц В(Ц В(Ц В(Ц В(Ц В(Ц В(Ц В(Ц В(Ц . В(Ц В(Ц В(Цгм В( ьп ) В( ьп.) Р П.)-2 Всеми В(п~п") 4 ) а2/(и ) Рве. 4.В. Дерево рекурсии, генерируемое рекурреитнмм соотногаением Т(п) = ПТИп/6()-)-/(и). Аргумент рекурсии пл онределестси уравнением (427). Б Элк. 3222 не составляет труда, поскольку в первом случае для получения нужного результата можно использовать неравенство )и/Ь1 > и/Ь, а во втором — неравенспю (и/Ь( ( и/Ь.
Чтобы получить нижнюю границу рекуррентного соотношения (4.26), необходимо применить те же методы, что и при нахождении верхней границы для рекуррентного соотношения (4.25), поэтому здесь будет показан поиск только последней. Дерево рекурсии, представленное на рис.4.7, модифицируется и приобретает вид„ показанный на рис.4.8. По мере продвижения по дереву рекурсии вниз мы получаем следукнцую рекурсивную последовательность аргументов: Часньь 1 Основы Обозначим в'-й элемент этой последовательности как и, где если э=О, ~гЬ т/61, если т' > 0 . (4.27) пс < п, — +1 Ь п 1 — + — +1, Ьз Ь п 1 1 — + — + — +1 Ьз 6з Ь пт < пг < пз < В общем случае имеем 1-1 1 + ~'- 6* ь=с 1 +'у —, ь=о Ь +: Ь вЂ” 1 п и < —.
М Полагая 1 = ~1ойь п), получаем п йоаь и! п Ь < +— ЬЬоаь н-з Ь вЂ” 1 п 6 = — + п/Ь Ь вЂ” 1 Ь =Ь+ Ь вЂ” 1 = 0(1), и, таким образом, мы видим, что на глубине ~1ойь и) размер задачи не превышает константы. Наша первая цель заключается в определении глубины )в, такой, что пь — кон- станта. Воспользовавшись неравенством ~х1 < х+ 1, получаем Глава 4.
Разделай и азасвзвуй Из рис. 4.8 видно, что Оаав а) — 1 2 (и) Я(и~аяза) + ~ о2/(п ) (4.28) что почти то же самое, что и уравнение (4.21), с тем отличием, что и является произвольной целой константой, не ограниченной только точными степенями Ь. Теперь можно вычислить сумму Оаяз а) -1 д(п) = ~~з аз/(п,) З=о (4.29) из уравнения (4.28) аналогично тому, как это делалось в доказательстве леммы 4.3. Начнем со случая 3. Если а/Цп/61) < сУ(п) для и > 6+ Ь/(Ь вЂ” 1), где с < 1 — константа, то ае/(ид) < сз/(п). Следовательно, сумму в уравнении (4.29) можно вычислять, как в лемме 4.3. В случае 2 имеем У(и) = ез(п"яв ').
Если мы сможем показать, что /(пд) = 0(п"Ява/о') = 0((п/У) аа '), то доказательство случая 2 леммы 4.3 будет завершено. Заметим, что из 1 < (!обои) следует Ьз/п < 1. Наличие границы /(п) = 0(п"ага) подразумевает, что существует такая константа с > О, что для всех достаточно больших и 1ааь а /(п ) <с( —.+ — ) с —. 1+— ь Ьз Ь (";" ) (" — ')"" поскольку с(1+ Ь/(Ь вЂ” 1) ) заяз представляет собой константу. Таким образом, случай 2 доказан.
Доказательство случая 1 почти идентично. Ключевым моментом является доказательство границы /(п ) = 0((п/Ьз)~'Яз' '), которое аналогично соответствующему доказательству случая 2, хотя алгебраические выкладки при этом оказываются несколько более сложными. Итак, мы доказали соблюдение верхних границ в основной теореме для всех целых и. Соблюдение нижних границ доказывается аналогично. Часть 1 Основы Упражнения 4.б.1 * Приведите простое и точное выражение для п в уравнении (4.27) для случая, когда Ь вЂ” положительное целое число (а не произвольное действительное). 4.б.2 * Покажите, что если выполняется соотношение /(п) = 9(п"яь 1я~ п), где Ь > О, то основное рекуррентное соотношение имеет решение Т(п) = 9(иман' 1б~+ и).
Для простоты рассмотрите только случай точных степеней Ь. 4.4.3 * Покажите, что в случае 3 основной теоремы одно из условий излишнее в том смысле, что из условия регулярности а/(п/Ь) < с/(п) для некоторой константы с < 1 следует, что существует константа е ) О, такая, что /(и) = П(пма '+'). Задачи 4.1. Примеры рекурреитимх соотиовиеиий Определите верхнюю и нижнюю асимптотические границы функции Т(п) для кахслого из представленных ниже рекуррентных соотношений. Считаем, что Т(п) при п < 2 является константой.
Попытайтесь сделать эту оценку как можно более точной и обоснуйте свой ответ. а. Т(п) = 2Т(п/2) +п . б. Т(п) = Т(7п/10) + п. в. Т(п) = 16Т(п/4) + пг. г. Т(п) = 7Т(п/3) + пг. д. Т(п) = 7Т(п/2)+ из е. Т(п) = 2Т(п/4) +,/п. ж. Т(п) = Т(п — 2) + пг. 4.2. Стоимости передачи параметров В этой книге предполагается, что передача параметров при вызове процедуры занимает фиксированное время, даже если передается Х-элементный массив. Для большинства вычислительных систем это предположение справедливо, поскольку передается не сам массив, а указатель на него.
В данной задаче исследуются три стратегии передачи параметров. 1. Массив передается посредством указателя. Время = 9(1). Глава К Разделяй и властвуй 2. Массив передается посредством копирования. Время = 9(Х), где Х вЂ” размер массива. 3. Массив передается путем копирования только некоторого поддиапазона, к которому обращается вызываемая процедура. Время = сз(д — р+ 1) прн передаче подмассива А(р ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
