Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 53
Текст из файла (страница 53)
С помощью модифицированной версии процедуры Рлкт1т1О1Ч входной массив делится относительно медианы медиан к. Пусть число Е на единицу превышает количество элементов, попавших в нижнюю часть разбиения. Тогда к — Е-й 251 !лала 9. Медианы и лорядяоеые статистики .,,)В .:,з)ь",; 'Ц~::;-",.'ь~:,'.! (ь ~1:гв'::::; '~1::;:;:!е::"::::,:::'». рве. 9.1. Анализ алгоритма Бн.ист. На рисунке и элементов представлены в виде маленьких кружюв, а каждая группа нз 5 элементов — отдельным столбном. Медианы групп обозначены белымн крупками, а медиана медиан х снабжена соответствующей меткой. (При определении медианы четного количества элементов используется нююшя медиана.) Стрелки проведены в направлении от больших элементов к меньшим. Из рисунка видно, что в каждой полной группе из 5 элементов, расположенной справа от х, содержится по 3 элемента, превышающих по величине х, а в каждой полной группе из 5 элементов, расположенной слева ат х, содержится по 3 элемента, меньших по величине, чем х.
Элементы, которые превышают х, выделены серым фоном. в порядке возрастания элемент, и в верхнюю часть разбиения попадаег и — )с элементов. 5. Если з = й, то возвращается значение х. В противном случае процедура Ян.бст вызывается рекурсивно, и с ее помощью выполняется поиск з'-го в порядке возрастания элемента в нижней части, если з < гс, или (т' — гс)-го в порядке возрастания элемента в верхней части, если з > )с. Чтобы проанализировать время работы процедуры Збьбст, сначала определим нижнюю границу для количества элементов, превышающих по величине опорный элемент х.
Разобраться в этой бухгалтерии поможет рис. 9.1. Как минимум половина медиан, найденных на шаге 2, больше или равны медиане медиан х'. Таким образом, ввк минимум ~и(51 групп содержат по 3 элемента, превышающих величину х, за исключением одной группы, в которой меньше пяти элементов (такая группа существует, если и не делится на 5 нацело), н еще одной группы, содержащей сам элемент х. Не учитывая эти две группы, приходим к выводу, что количество элементов, величина которых превышает х, равно как минимум З(Ь Г511-2) ~ 10 Аналогично имеется не менее Зи/10 — 6 элементов, величина которых меньше х.
Таким образом, процедура 35ЫСт рекурсивно вызывается на шаге 5 не более чем для 7и/10+ 6 элементов. В силу прслпалсиення о тем„что асс числа различаются, каждая лз этих медиан болыпе илн меньше х, зь лсялючснием самой медалям х. Часть ЕЕ Сортировка и корвдковак статистика 752 Теперь можно сформулировать рекуррентное соотношение для времени работы алгоритма Бееест (обозначим его как Т(п)) в наихудшем случае.
Для выполнения шагов 1, 2 и 4 требуется время 0(п) (шаг 2 состоит из 0(п) вызовов сортировки вставкой для множеств размером 0(1)). Выполнение шага 3 занимает время Т(~п/5) ), а выполнение шага 5 — время не более Т(7п/10 + 6) (предполагается, что функция Т монотонно неубывающая). Сделаем, на первый взгляд, необоснованное предположение о том, что для обработки любого входного массива, количество элементов которого меньше 140, требуется время 0(1) (вскоре нам раскроется магия константы 140).
Таким образом мы получаем рекуррентное соотношение 0(1), если и < 140, Т(п) < Т((п/5)) + Т(7п/10+ 6) + 0(п), если п > 140 . Покажем методом подстановки, что время работы, описываемое этим соотношением, линейно зависит от количества входных элементов. Точнее говоря, покажем, что для неюторой достаточно большой константы с и для всех и > 0 выполняется неравенство Т(п) < сп. Начнем с предположения, что это неравенство выполняется для некоторой достаточно большой константы с и для всех п < 140; зто предположение действительно выполняется, если константа с выбрана достаточно большой. Кроме того, выберем константу а таким образом, чтобы функция, соответствующая представленному выше слагаемому 0(п) (которое описывает нерекурсивную составляющую времени работы алгоритма) для всех п > 0 была ограничена сверху величиной ап.
Подставив эту гипотезу индукции в правую часть рекуррентного соотношения, получим Т(п) < с [и/5( + с(7п/10 + 6) + ап < /5+ с+ 7сп/10+ бс+ ап = 9сп/10 + 7с+ сп = сп + ( — сп/10 + 7с + ап) . Это выражение не превышает величину сп, если выполняется неравенство — сп/10+ 7с+ ап < 0 . (9.2) При и > 70 неравенство (9.2) эквивалентно неравенству с > 10а(п/(п — 70)). Поскольку мы предположили, что и > 140, то и/(п — 70) < 2, а значит, если выбрать с > 20а, то будет удовлетворяться неравенство (9.2). (Заметим, что в константе 140 нег ничего особенного; вместо нее можно было бы взять любое другое целое число, превышающее 70, после чего соответствующим образом нужно было бы выбрать юнстанту с.) Таким образом, в наихудшем случае время работы алгоритма Бееест линейно зависит от количества входных элементов.
Как и в алгоритмах сортировки сравнением, которые рассматривались в разделе 8.1, в алгоритмах Яееест и Клмпомыеп-Бееест информация о взаимном расположении элементов извлекается только путем их сравнения. Как было дока- 255 Глава Я Медиаиы и ларлдиавые етатиетиви зано в главе 8, в модели сравнений сортировка выполняется в течение времени П(п18п), даже в среднем (см. задачу 8.1). В этой же главе был рассмотрен алгоритм сортировки, время работы которого линейно зависит от количества сортируемых элементов, но в нем делаются дополнительные предположения относительно входных данных. Для работы представленных в настоящей главе алгоритмов выбора, время работы которых такое же, напротив, никаких дополнительных предположений не требуется.
К этим алгоритмам не применима нижняя граница П(п!8п), поскольку задача выбора в них решается без сортировки. Таким образом, решение задачи выбора путем сортировки и индексирования, представленное во введении к данной главе, асимптотически неэффективное. Упражнения 9.3.3 В алгоритме БЕЕЕСТ все входные элементы делятся на группы по 5 элементов. Было бы время работы этого алгоритма линейным, если бы входной массив делился на группы по 7 элементов? Докажите, что время работы алгоритма не будет линейным, если в каждой группе будет по 3 элемента. 9.3.2 Проанализируйте алгоритм Ба.ест и покажите, что при и > 140 как минимум ~п/41 элементов превышают по величине медиану медиан х н как минимум ~п(41 элементов меньше х. 9.3.3 Покажите, каким образом можно выполнить быструю сортировку за время 0(п!8 и) в наихудшем случае, считая, что все элементы различны.
Предположим, что в алгоритме, предназначенном для поиска среди и элементов 1-го в порядке возрастания элемента, применяется только операция сравнения. Покажите, что с помощью этого алгоритма можно также найти 1 — 1 наименьших элементов и и — 1 наибольших элементов, не выполняя никаких дополнительных сравнений. 9.3.5 Предположим, что у нас имеется подпрограмма поиска медиан, которая представляет собой "черный ящик" и время работы которой линейно зависит от количества входных элементов. Приведите пример алгоритма с линейным временем работы, с помощью которого задача выбора решалась бы для произвольной порядковой статистики.
9.3.6 По определению )е-мн кванлеплялеи (йпап6!ез) п-элементного множества называются )е — 1 порядковых статистик, разбивающих это отсортированное множество на Й одинаковых по размеру подмножеств (с точностью до одного элемента). 254 Часть Рй Сортяровка и лорядкокая статистика Сформулируйте алгоритм, который бы выводил список /с-х квантилей множества за время 0(п !й /с). 9.3. 7 Опишите алгоритм, который для заданного множества Я, состоящего из п различных чисел, и положительной целой константы )с < и определял бы /с ближайших соседей медианы множества Я, принадлежащих этому множеству.
Время работы алгоритма должно быть равно 0(п). 9.3.8 Пусть Х[1 ..п~ и г 11 .. и~ — два массива, каждый из которых содержит по и элементов, расположенных в отсортированном порядке. Разработайте алгоритм, в котором поиск медианы всех 2п элементов, содержащихся в массивах Х и У, выполнялся бы за время 0(1б и). 9.3.9 Профессор работает консультантом в нефтяной компании, которая планирует провести магистральный трубопровод от восточного до западного края нефтяного месторождения с п скважинами. От каждой скважины к магистральному трубопроводу кратчайшим путем, в направлении на север или на юг, проведены рукава (рис. 9.2).
Каким образом профессор может выбрать оптимальное расположение трубопровода (т.е. такое, при котором общая длина всех рукавов была бы минимальной) по заданным координатам скважин (х, у)? Покажите, что это можно сделать в течение времени, линейно зависящего от количества скважин. Рис. 9.2. Определение положения нефтепровода, при котором общая длина поперечных рукавов будет минимальной 255 Глава К атедааны а паалдлавые етатыстааа Задачи 9.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
