Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 51
Текст из файла (страница 51)
Взвеигенной Гнижней) медианой (юецЫеб (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). Если все ключи различны, то динамическое множество представимо в виде набора ключевых значений. Иногда объекты содержат сопутствующие данные (заее!!йе ба!а), которые находятся в других его полях, но не используются реализацией множества. Кроме того, обьект может содержать поля, доступные для манипуляции во время выполнения операций над множеством; иногда в этих полях хранятся данные или указатели на другие объекты множества. В некоторых динамических множествах предполагается, что их ключи являются членами полностью упорядоченного множества, например, множества действительных чисел или множества всех слов, которые могут быть расположены в алфавитном порядке.
(Полностью упорядоченные множества удовлетворяют свойству трихотомии, определение которого дано в разделе 3.1.) Полное упоря- Часть ! П. Структуры данных 257 дочение, например, позволяет определить минимальный элемент множества нли говорить о ближайшем элементе множества, превышающем заданный.
Операции в динамических множествах Операции динамического множества можно разбить на две категории: запросы (йиепез), которые просто возвращают информацию о множестве, н мадифлцируюлтие операции (шоп1(у1лд орегацопз), изменяющие множество. Ниже приведен список типичных операций. В каждом конкретном приложении требуется, чтобы были реализованы лишь некоторые из них. БеАксн(Я, й) Запрос, который возвращает указатель иа элемент х заданного множества о', для которого Йеу [х] = Й, или значение хп., если в множестве о' такой элемент отсутствует. )нзект(Я, х) Модифицирующая операция, которая пополняет заданное множество Я одним элементом, на который указывает х.
Обычно предполагается, что выполнена предварительная инициализация всех полей элемента х, необходимых для реализации множества. Редеете(Я, х) Модифицирующая операция, удаляющая из заданного множества о элемент, на который указывает х. (Обратите внимание, что в этой операции используется указатель на элемент, а не его ключевое значение.) Мммим(Я) Запрос к полностью упорядоченному множеству Я, который возвращает указатель на элемент этого множества с наименьшим ключом. МАх~мим(5) Запрос к полностью упорядоченному множеству Я, который возвращает указатель на элемент этого множества с наибольшим ключом.
БиССЕЗЗОК(Я, х) Запрос к полностью упорядоченному множеству Я, который возвращает указатель на элемент множества Я, ключ которого является ближайшим соседом ключа элемента х и превышает его. Если же х — максимальный элемент множества Я, то возвращается значение нп.. РкепесеяБОк(Я, х) Запрос к полностью упорядоченному множеству Я, который возвращает указатель на элемент множества Я, ключ которого является ближайшим меньшим по значению соседом ключа элемента х. Если же х — минимальный элемент множества Я, то возвращается значение ми.. Часть П1. Структуры данных 258 Запросы Биссеззок и Ркепесеззок часто обобщаются на множества, в которых не все ключи различаются. Для множества, состоящего из и элементов, обычно принимается допущение, что вызов операции М~ьлмим, после которой и — 1 раз вызывается операция БУссеззок, позволяет пронумеровать элементы множества в порядке сортировки.
Время, необходимое для выполнения операций множества, обычно измеряется в единицах, связанных с размером множества, который указывается в качестве одного из аргументов. Например, в главе 13 описывается структура данных, способная поддерживать все перечисленные выше операции, причем время их выполнения на множестве размера и выражается как О (1Б и). Обзор третьей части В главах 10-14 описываются несколько структур данных, с помощью которых можно реализовать динамические множества. Многие из этих структур данных будут использоваться впоследствии при разработке эффективных алгоритмов, позволяющих решать разнообразные задачи. Еще одна важная структура данных, пирамида, уже была рассмотрена в главе 6. В главе 10 представлены основные приемы работы с такими простыми структурами данных, как стеки, очереди, связанные списки и корневые деревья.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
