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