Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 26
Текст из файла (страница 26)
Рекуррентные соотношения /(и) /(л) а/(л/Ь) /(и, ) /(п, ) +, +, + (!оа, /(пг) /(пг) - /(л,) ЙЙ И О(!) и(!) 9(!) О(!) Е(!) 9(!) О(!) Е(!) 9(!) 6(!) - Е(!) 9(!) 0(В -Зп Е(п""'] 6(л~"") Всего: В(ппп')и'„Г~а'/(п/Ь') Рис. 4.4. Дерево рекурсии, определенное рекуррентным соотношением Т (и) = аТ (!'и/Ь1 ) + / (и). Аргумент рекурсии и определяется уравнением (4.12) ио < и) < и, и — +1 6 и 1 — + — +1 Ьз Ь и 1 1 — + — + — +1 Ьз Ьз Ъ и2 < из < В общем случае получаем: 1 и 1 и Ь + ) — < — + ) —.= —.+— Ь' Ь) Ь' Ь) Ь вЂ” 1 (=о (=О и и < —.
Полагая, что )' = ~1обь и), мы получим: Ь и Ь и Ь Ь и,. „< + < + — — + Ь+ =О(1), Ь()оке л) Ь вЂ” 1 Ь!.ке -) Ь вЂ” 1 и/Ь Ь вЂ” 1 Ь вЂ” 1 Сейчас наша цель — определить глубину /с, такую что иь — константа. Используя неравенство )х1 < х+ 1, получаем: Часть !. Основы 132 откУда видно, что на УРовне (!сбыл~ РазмеР задачи не пРевышает постоЯннУю величину. Из рис.
4.4 видно, что выполняется соотношение (1ояо о) -1 Т(и) Р (и~ох~о) + '~~ оз г(п,) (4.13) того же вида, что и уравнение (4.б) (с тем отличием, что здесь и — произвольное целое число, а не точная степень числа 6). Теперь можно приступить к оценке суммы (1оя~ и! — 1 д(и) = ~~~ аз/(п ), у=о (4.14) фигурирующей в уравнении (4.13). Эта сумма будет оцениваться аналогично тому, как это делалось при доказательстве леммы 4.3. Начнем с рассмотрения случая 3. Если для п > Ь+ Ь/(Ь вЂ” 1) выполняется соотношение а/((п/61) < с/(и), где с < 1 — константа, то отсюда следует, что а1/(п ) < сз/(п). Таким образом, сумму в уравнении (4.14) можно оценить точно так же, как это было сделано в лемме 4.3. В случае 2 выполняется условие /(п) = 9 (и'ао ). Если мы смо- жЕМ ПОКаЗатЬ, ЧтО /(П ) = О (И1оя~ "/иу) = О ((И/У) ~' ), тО дОКаЗатЕЛЬСтВО случая 2 леммы 4.3 будет завершено.
Заметим, что из неравенства д < (1обь п1 следует неравенство У/п < 1. Наличие границы /(и) = О (и!ой') подразумевает, что существует такая константа с > О, что при достаточно больших и, выполняются такие соотношения: ; 1оаьо У(пу) < с — + ) 163 Ь-1) =с — 1+ —. = ('"')("(-'- -' ))""' "(".")(" -' )'"'= ='("'"') поскольку с(1+ 6/(Ь вЂ” 1)) 'а' — константа. Таким образом, случай 2 доказан. Доказательство случая 1 почти идентично только что рассмотренному. Главное— Глава 4.
Рекуррентные соотношения 133 доказать справедливость границы яп ) = О (п~'а~ ' '). Это делается аналогично доказательству в случае 2, хотя алгебраические выкладки при этом оказываются несколько более сложными. Итак, мы доказали соблюдение верхних границ в основной теореме для всех целых и. Соблюдение нижних границ доказывается аналогично. Упражнения *4.4-1. Приведите простое и точное выражение для и в уравнении (4.12) для случая, когда Ь вЂ” положительное целое число (а не произвольное действительное).
* 4.4-2. Покажите, что если выполняется соотношение / (и) = 9 (и'к~ 16ь п), где й > О, то решение основного рекуррентного соотношения — Т (и) = = 9 (пыа~' 1к +1п). Для простоты рассмотрите только случай целых степеней Ь. * 4.4-3. Покажите, что в случае 3 основной теоремы одно из условий излишнее в том плане, что из условия регулярности а/ (и/Ь) < с/ (и) для некоторой константы с < 1 следует, что существует константа е > О, такая что /(и) = П (пма'а+').
Задачи 4-1. Примеры рекуррентных соотношений Определите верхнюю и нижнюю асимптотические границы функции Т (и) для каждого из представленных ниже рекуррентных соотношений. Считаем, что при и < 2Т(п) — константа. Попытайтесь сделать эту оценку как можно более точной и обоснуйте свой ответ. а) Т(п) = 2Т(п/2) + па. б) Т (и) = Т (9п/10) + и. в) Т(п) = 16Т(п/4) +пг г) Т (п) = 7Т (п/3) + пз. д) Т(п) = 7Т(п/2) + па, е) Т(п) = 2Т(п/4)+ ~/и. ж) Т(п) = Т(п — 1) + и.
з) Т(п) =Т(,/й)+1. 4-2. Поиск отсутствующего целого числа Массив А (1..п] содержит все целые числа от 0 до т1 за исключением одного. Отсутствующее число можно легко определить за время О (и), 134 Часть 1. Основы располагая вспомогательным массивом В [1..п], предназначенным для записи имеющихся чисел из массива А. Однако в этой задаче мы лишены средств, позволяющих получить доступ к целому числу из массива А посредством одной операции.
Элементы массива А представлены в двоичной системе счисления, и единственная операция, с помощью которой можно осуществлять к ним доступ, это "извлечение 3'-го бита элемента А [г]", юторая выполняется в течение фиксированного времени. Покажите, что, располагая только этой операцией, отсутствующее целое число все же можно определить за время О (и). 4-3. Время, затрачиваемое на передачу констант В этой книге предполагается, что передача параметров при вызове процедуры занимает фиксированное время, даже если передается И-элементный массив. Для большинства вычислительных систем это предположение справедливо, поскольку передается не сам массив, а указатель на него.
В данной задаче исследуются три стратегии передачи параметров. 1) Массив передается посредством указателя. Время выполнения этой операции Т = 6 (1). й) Массив передается путем юпирования. Время выполнения этой операции Т = 9 ()т'), где Ж вЂ” размер массива.
ш) Массив передается путем копирования только некоторого поддиапазона, к которому обращается вызываемая процедура. Время передачи подмассива А [р..о] равно Т = О (д — р+ 1). а) Рассмотрите рекурсивный алгоритм бинарного поиска, предназначенный для нахождения числа в отсортированном массиве (см. упражнение 2.3-5). Приведите рекуррентные соотношения, описывающие время бинарного поиска в наихудшем случае, если массивы передаются с помощью каждого из описанных выше методов, и дайте точные верхние границы решений этих рекуррентных соотношений. Пусть размер исходной задачи равен Ф, а размер подзадачи — и. б) Выполните задание части а) для алгоритма Миксе Болт, описанного в разделе 2.3.1. 4-4.
Примеры рекуррентных соотношений Дайте верхнюю и нижнюю асимптотические оценки функции Т (и) в каждом из приведенных ниже рекуррентных соотношений. Предполагается, что для достаточно малых значений и Т (и) — постоянная величина. Постарайтесь, чтобы оценки были как можно более точными и обоснуйте ответы. а) Т(п) = ЗТ(п/2) + п1бп. Глава 4. Рекуррентные соотношения 135 4-5.
Числа Фибоначчи В этой задаче раскрываются свойства чисел Фибоначчн, определенных с помощью рекуррентного соотношения (3.21). Воспользуемся для решения рекуррентного соотношения Фибоначчи методом генераторных функций. Определим производящую функцию (или формальный степенной ряд) У' как .к = ~ Р~з =О+а+а +2з +За +ба +8з +13е +21з +..., =о где Г, — г'-е число Фибоначчи. а) Покажите, что г (г) = з + зУ'(з) + зз.к Я. б) Покажите, что где Ф = = 1.61803... 2 Ф = = -0.61803...
2 в) Покажите, что У'(з) = 2 -1 (фз ф1) 1 '=о г) Докажите, что Е, = ф'/~/5 (округленное до ближайшего целого) для всех 1 > О. (Указание: обратите внимание на то, что ~ф~ < 1.) б) Т(п) в) Т(п) г) Т(п) д) Т(п) е) Т(п) ж) Т(п) з) Т(п) и) Т(п) к) Т(п) = 5Т (п/5) + п/18 и. = 4Т(п/2) + пз~lй.
= ЗТ (п/3 + 5) + и/2. = 2Т (и/2) + и/18п. = Т (и/2) + Т (и/4) + Т (и/8) + п. = Т (и — 1) + 1/и. = Т(п — 1) + 1бп. = Т(п — 2) + 218п. =,/пТ (;/й) + п. Часть 1. Основы 136 д) докажите, что Р;.ьз ) фз для з' > О. 4-6. Тестирование СБИС В распоряжении профессора есть зз предположительно идентичных СБИС', которые в принципе способны тестировать друг друга. В тестирующее приспособление за один раз можно поместить две микросхемы.
При этом каждая микросхема тестирует соседнюю и выдает отчет о результатах тестирования. Исправная микросхема всегда выдает правильные результаты тестирования, а результатам неисправной микросхемы доверять нельзя. Таким образом, возможны четыре варианта результатов тестирования, приведенные в таблице ниже.
Отчет Отчет Вывод микросхемы А микросхемы Б Б исправна Либо обе микросхемы исправны, либо обе неисправны Неисправна хотя бы одна микросхема Неисправна хотя бы одна микросхема Неисправна хотя бы одна микросхема А исправна Б исправна Б неисправна Б неисправна А неисправна А исправна А неисправна а) Покажите, что если неисправно более зз/2 микросхем, то с помощью какой бы то ни было стратегии, основанной на попарном тестировании, профессор не сможет точно определить, какие микросхемы исправны.
(Предполагается, что неисправные микросхемы не смогут тайно сговориться, чтобы обмануть профессора.) б) Рассмотрим задачу о поиске одной исправной микросхемы среди и микросхем, если предполагается„что исправно более половины всех микросхем. Покажите, что ~п/2) попарных тестирований достаточно для сведения этой задачи к подзадаче, размер которой приблизительно в два раза меньше. в) Покажите„что можно найти все исправные микросхемы с помощью 9 (и) попарных тестирований, если предполагается, что более половины микросхем исправны. Сформулируйте и решите рекуррентное соотношение, описывающее количество тестирований.
1 СБИС вЂ” зто аббревиатура от "сверхбольшие интегральные схемы" (микросхемы, созданные по технологии, которая используется при производстве большинства современных микропропессоров). Глава 4. Рекуррентные соотношения 137 4-7. Массивы Монжа Массив А, состоящий из действительных чисел и имеющий размер т х х и, называется массивом Монжа (Мопйе апау), если для всех ю', ), lс и 1, таких что 1 < г < /с < тп и 1 < 7' < 1 < и, выполняется соотношение А[а,Я+ А [В,1] < А[т',1]+ А[1, 7']. Другими словами, при любом выборе двух срок и двух столбцов из массива Монжа (при этом элементы массива на пересечении выбранных строк и столбцов образуют прямоугольник) сумма элементов в левом верхнем и правом нижнем углах полученного прямоугольника не превышает сумму элементов в левом нижнем и правом верхнем его углах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
