Алгоритмы - построение и анализ (1021735), страница 49
Текст из файла (страница 49)
Предположим, что у нас имеется подпрограмма поиска медиан, которая представляет собой "черный ящик" и время работы которой линейно зависит от количества входных элементов. Приведите пример алгорит- ма с линейным временем работы, с помощью которого задача выбора решалась бы для произвольной порядковой статистики.
По определению й-ми квалтылями (пнап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. Взвеигенной Гнижней) медианой (юецЫеб (1оюег) шесйап) называется элемент хы удовлетворяющий неравенствам а) Докажите, что обычная медиана элементов хы хз,..., х„равна взвешенной медиане х„веса которой для всех 1 = 1,2,..., и равны вч = 1/и. б) Покажите, как вычислить взвешенную медиану и элементов с помощью сортировки, чтобы время вычисления в наихудшем случае было равно О (и 1я и). в) Покажите, как с помощью алгоритма, в котором производится поиск медианы за линейное время (подобного описанному в разделе 9.3 алгоритму БЕЬЕСТ), вычислить взвешенную медиану в течение времени, которое равно 6 (и) в наихудшем случае.
Задача об оптимальном размещении почтового отделения формулируется так. Имеется и точек рырэ,...,р„, которым отвечают веса юы юз,..., ю„. Нужно найти точку р (это не обязательно должна быть одна из входных точек), в которой минимизируется сумма 2,'," ю;с1 (р, р,), где Н (а, Ь) — расстояние между точками а и Ь.
г) Докажите, что взвешенная медиана — это наилучшее решение одномерной задачи об оптимальном размещении почтового отделения. В этой задаче точки представляют собой действительные числа, а расстояние между точками а и Ь определяется как И (а, Ь) = )а — Ь!. д) Найдите наилучшее решение двумерной задачи об оптимальном размещении почтового отделения.
В этой задаче точки задаются парами координат (х, у), а расстояние между точками а = (хм у1) и Ь = (хэ,уз) представляет собой манхэттенское расстояние (Мапйапал йзгапсе), которое определяется соотношением д (а, Ь) = = (хг — хз(+ )у1 — уз!. 9-3. Малые порядковые статистики Ранее было показано, что количество сравнений Т (и), которые производятся в алгоритме 5еьест в наихудшем случае в ходе выбора 1-й порядковой статистики из п элементов, удовлетворяет соотношению Т(п) = = 6(п).
Однако при этом скрытая в О-обозначении константа имеет Часть 11. Сортировка и порядковая статистика 254 довольно большую величину. Если с намного меньше п, то можно реализовать другую процедуру, в которой в качестве подпрограммы используется процедура Бпс.вст, но в которой в наихудшем случае производится меньшее количество сравнений. а) Опишите алгоритм, в котором для поиска с-го в порядке возрастания среди п элементов требуется (/с (и) сравнений, где Т (и) если г > и/2, [п/2~ + (7с ( [п/21) + Т (2с) в противном случае. с (Указание: начните с [п/2[ непересекающихся попарных сравнений и организуйте рекурсивную процедуру для множества, содержащего меньшие элементы из каждой пары.) б) Покажите, что если г ( и/2, то сзс (и) = п + 0 (Т (21) 1к (и/г)). в) Покажите, что если с' — константа, меньшая, чем и/2, то (зс (и) = = и+ 0(1кп).
г) Покажите,что если с = и/й для й > 2,то (/с(п) = и+0(Т(2п/)с) х х 1бй). Заключительные замечания Алгоритм поиска медиан, время работы которого в наихудшем случае линейно зависит от количества входных элементов, был разработан Блюмом (В!шп), Флойдом (Рсоуд), Праттом (Ргасс), Ривестом (Ксчезс) и Таржаном (Тагсап) [43). Версия этого алгоритма с пониженным средним временем работы появилась благодаря Хоару (Ноаге) [1461. Флойд и Ривест [92) создали улучшенную версию этого алгоритма, работающую в среднем еще производительнее, в которой разбиение производится относительно элемента, рекурсивно выбираемого из небольшого подмножества.
До сих пор точно неизвестно, сколько именно сравнений необходимо для поиска медианы. Нижняя граница, равная 2п сравнениям, была найдена Бентом (Вепс) и Джоном ()оссп) [38], а верхняя граница, равная Зп сравнениям, — Шенхагом (Бе)сои[саяе), Патерсоном (Расегзоп) и Пиппенджером (Рсррепкег) [265). Дор (13ог) и Цвик (Естся) [79) улучшили обе эти границы; их верхняя граница немного меньше величины 2.95п, а нижняя — несколько превышает величину 2п. В своей работе [239) Патерсон описал все изложенные здесь результаты, а также результаты других работ, посвященных этой теме. Введение Множество — это фундаментальное понятие как в математике, так и в теория вычислительных машин. Тогда как математические множества остаются неизменными, множества, которые обрабатываются в ходе выполнения алгоритмов, могут с течением времени разрастаться, уменьшаться или подвергаться другим изменениям.
Назовем такие множества динамическими (бупаппс). В пяти последующих главах описываются некоторые основные методы представления конечных динамических множеств и манипуляции с ними на компьютере. В некоторых алгоритмах, предназначенных для обработки множеств, требуется выполнять операции нескольких различных видов. Например, набор операций, используемых во многих алгоритмах, ограничивается возможностью вставлять элементы в множество, удалять их, а также проверять, принадлежит ли множеству тот или иной элемент. Динамическое множество, поддерживающее перечисленные операции, называется словарем (йсйопагу). В других множествах мо.
гут потребоваться более сложные операции. Например, в неубывающих очередях с приоритетами, с которыми мы ознакомились в главе 6 в контексте пирамидальной структуры данных, поддерживаются операции вставки элемента и извлечение минимального элемента. Оптимальный способ реализации динамического множества зависит от того, какие операции должны им поддерживаться. Элементы динамического множества В типичных реализациях динамического множества каждый его элемент представлен некоторым обьектом; если в нашем распоряжении имеется указатель на обьекг, то можно проверять и изменять значения его полей. (В разделе 10.3 обсуждается реализация объектов и указателей в средах, где они не являются базовыми типами данных.) В динамических множествах некоторых типов предполагается, что одно из полей объекта идентифицируется как ключевое (кеу бе!6).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
