Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 54
Текст из файла (страница 54)
Наибольшие д чисел в норядке сортировки Пусть имеется множество из и чисел, в котором с помощью алгоритма, основанного на сравнениях, нужно найти г наибольших элементов, расположенных в порядке сортировки. Сформулируйте алгоритм, в котором реализовывался бы каждый из перечисленных ниже методов с наилучшим возможным асимптотическим временем работы в наихудшем случае. Проанализируйте зависимость времени работы этих аагоритмов от и и г. а.
Отсортируйте эти числа и выведите 1 наибольших. Гь Создайте из чисел невозрастающую очередь с приоритетами и 1 раз вызовите процедуру Ехтклст-Млх. и Найдите с помощью алгоритма порядковой статистики з-й по порядку наибольший элемент, произведите разбиение относительно него и выполните сортировку г наибольших чисел. 9.2. Взвешенная медиана Пусть имеется и различных элементов хы хз,..., х„, для которых заданы положигельные веса юы юз,..., ю„, такие, что 2 ',". юе = 1.
Взвешенной (нижней) медианой (юе1я)згей ((озчег) шед|ап) называется элемент хы удовлетворяющий неравенствам 2 1 1 ю,(— е,)ел Например, если элементами являются 0.1, 0.35, 0.05, 0.1, 0.15, 0.05, 0.2 и каждый элемент имеет вес, равный значению самого элемента (т.е. ю, = х; для з = 1, 2,..., 7), то медианой является 0.1, а взвешенной медианой — 0.2.
а. Докажите, что обычная медиана элементов хы хз,..., х„равна их взвешенной медиане, если все веса равны ю, = 1/п, з = 1, 2,..., п. б. Покажите, как вычислить взвешенную медиану п элементов с помощью сортировки, чтобы время вычисления в наихудшем случае было равно 0(п!и п). в. Покажите, как с помощью алгоритма, в котором поиск медианы производится за линейное время (подобного описанному в разделе 9.3 алгоритму Бкькст)„ вычислить взвешенную медиану в течение времени, которое в наихудшем случае равно Э(п). 25б Части П. Сортировка и яоаядковая статистика Задача о размещении почтового отделения формулируется следукицим образом.
Имеется и точек рм рз,..., рко которым соответствуют веса иЧ, воз,..., ш„. Нужно найти точку р (это не обязательно должна быть одна из входных точек), в котоРой минимизиРУетсЯ сУмма 2,," з ш, о(Р, Р,), где д(а, Ь) — РасстоЯние междУ точками а и Ь. г. Докажите, что взвешенная медиана — это наилучшее решение одномерной задачи об оптимальном размещении почтового отделения.
В этой задаче точки представляют собой действительные числа, а расстояние между точками о и Ь определяется как с((а, Ь) = )о — Ь|. д. Найдите наилучшее решение двумерной задачи об оптимальном размещении почтового отделения. В этой задаче точки задаются парами координат (х, у), а расстояние между точками а = (хму1) и Ь = (хз, уз) представляет собой манхэттенское расстояние (Мап(запал сйз1апсе), которое определяется как 4(о, Ь) = ~хз — хз~ + (уз — уз1 9.3. Малые порядковые статистики Ранее было показано, что количество сравнений Т(п), которые производятся в алгоритме БПЬПСт в наихудшем случае в ходе выбора 1-й порядковой статистики из и элементов, удовлетворяет соотношению Т(п) = сз(п).
Однако при этом скрытая в Э-обозначении константа имеет довольно большую величину. Если 1 намного меньше и, то можно реализовать другую процедуру, в которой в качестве подпрограммы используется процедура БН.Кст, но в которой в наихудшем случае производится меньшее количество сравнений. а. Опишите алгоритм, в котором для поиска среди и элементов 1-го в порядке возрастания элемента требуется Ц(п) сравнений, где Т(п), если 1 > и/2, (и/2) + У,((п/2) ) + Т(21) в противном случае . (Указание: начните с 1п/2) непересекающихся попарных сравнений и организуйте рекурсивную процедуру для множества, содержащего меньшие элементы из каждой пары.) б.
Покажите, что если 1 < п/2, то Б,(п) = п + 0(Т(21) 1й(п/1)). в. Покажите, что если 1 — константа, меньшая п~2, то СЦп) = и+ 0(1кп). г. Покажите, что если 1 = п(1с для (с > 2, то Ц(п) = и+ 0(Т(2п/lс) 1кй). 9.4. Альтернативный анализ рандомизированного выбора В этой задаче для анализа процедуры Рслмпоминэ-Бн.пст в том же духе, как мы проводили анализ процедуры Клмпом12еп-Яп1скзокт в разделе 7.4.2, используются индикаторные случайные величины.
251 Глава а Медианы и норкдковые статистики Как и при анализе быстрой сортировки, предполагается, что все элементы различны, и мы переименовываем элементы входного множества А как гы гг,..., г„, где г, представляет собой 1-й в порядке возрастания элемент. Таким образом, вызов КАнпомивп-Явьпст(А, 1, и, )с) возвращает гь. Пусть для 1 < ( < 2 < п Х; а = 1( г, сравнивается с г в некоторый момент выполнения алгоритма поиска гь] . в. Запишите точное выражение для Е [Х; ь]. (Указание: ваше выражение может иметь различные значения в зависимости от значений 1, 2 и (с.) б.
Обозначим через Хь общее количество сравнений между элементами массива А при поиске гь. Покажите, что 5 ь и н . Ь-2 в. Покажите, что Е [Хь] < 4и. а Сделайте вывод о том, что в предположении различности всех элементов массива А ожидаемое время работы процедуры Клмпомыю-Бвьвст равно 0(п). Заключительные замечания Алгоритм поиска медиан, время работы которого в наихудшем случае линейно зависит от количества входных элементов, был разработан Блюмом (В)шп), Флойдом (Р)оуб), Пратгом (Ргап), Ривестом (Кпезг) и Таржаном (Таг]ап) [49]. Быстрая рандомизнрованная версия этого алгоритма появилась благодаря Хоару (Ноаге) [168]. Флойд и Ривест [107] разработали улучшенную рандомизированную версию этого алгоритма, в которой разбиение производится относительно элемента, рекурсивно выбираемого из небольшого подмножества.
До сих пор точно неизвестно, сколько именно сравнений необходимо для поиска медианы. Нижняя граница, равная 2п сравнениям„была найдена Бентом (ВепГ) и Джоном ()оЬп) [40], а верхняя граница, равная Зп сравнениям, — Шенхагом (Бс)юпЬайе), Патерсоном (Рагезвоп) и Пиппенджером (Р[ррепбег) [300]. Дор (1лог) и Цвик (Ели(с1с) улучшили обе эти границы. Их верхняя граница [92] немного меньше величины 2.9бп, а нижняя [93] имеет вид (2 + е)п, где е — малая константа (что представляет собой улучшение результата Дора и др. [91]). В своей работе [270] Патерсон описал некоторые из изложенных здесь результатов, а также результаты других работ, посвященных этой теме.
Введение Множество — зто фундаментальное понятие как в математике, так и в теории вычислительных машин. Тогда как математические множества остаются неизменными, множества, которые обрабатываются в ходе выполнения алгоритмов, могут с течением времени разрастаться, уменьшаться или подвергаться другим изменениям. Назовем такие множества динамическими (бупаш)с). В пяти последукнцих главах описываются некоторые основные методы представления конечных динамических множеств и работы с ними на компьютере.
В некоторых алгоритмах, предназначенных для обработки множеств, требуется выполнять операции нескольких различных видов. Например, набор операций, используемых во многих алгоритмах, ограничивается возможностью вставлять элементы в множество, удалять их, а также проверять, принадлежит ли множеству тот или иной элемент. Динамическое множество, поддерживающее перечисленные операции, называется словарем (йсйопагу).
В других множествах могут потребоваться более сложные операции. Например, в неубывающих очередях с приоритетами, с которыми вы ознакомились в главе б в контексте пирамидальной структуры данных, поддерживаются операции вставки элемента и извлечения минимального элемента. Оптимальный способ реализации динамического множества зависит от того, какие операции должны им поддерживаться.
Элементы динамического множества В типичных реализациях динамического множества каждый его элемент представлен некоторым объектом; если в нашем распоряжении имеется указатель на объект, то можно проверять и изменять значения его атрибутов, (В разделе 10.3 обсуяспается реализация обьектов и указателей в средах, где они не являются базовыми типами данных.) В динамических множествах некоторых типов предполагается, что один из атрибутов объекта идентифицирует ключ (кеу). Если все ключи различны, то динамическое множество представимо в виде множества ключевых значений. Объекты могут содержать сонуюсювующне данные (за[е111ге 2б1 Часаь Ш.
Структуры данных Ыа), которые находятся в других его атрибутах, но не используются реализацией множества. Кроме того, объект может содержать атрибуты, доступные для манипуляций во время выполнения операций над множеством; иногда в этих атрибутах могут храниться данные или указатели на другие обьекты множества. В некоторых динамических множествах предполагается, что их ключи являются членами полностью упорядоченного множества, например множества действительных чисел или множества всех слов, юторые могут быть расположены в алфавитном порядке. Полное упорядочение, например, позволяет определить минимальный элемент множества или говорить о ближайшем элементе множества, превышающем заданный. Операции няд динамическими множествами Операции над динамическим множеством можно разбить на две категории: запросы (ццепез), которые просто возвращают информацию о множестве, и модифицирующие операции (шоб1Гуищ орегайопз), изменяющие множество.
Ниже приведен список типичных операций. В каждом конкретном приложении требуется, чтобы были реализованы лишь некоторые из них. ЯеАксн(Я, Й) Запрос, который возвращает указатель на элемент х заданного множества Я, для которого х. Йеу = lс, или значение мп., если в множестве 5 такой элемент отсутствует. 1нзект(Я, х) Модифицирующая операция, которая пополняет заданное множество э одним элементом, на юторый указывает к. Обычно предполагается, что выполнена предварительная инициализация всех атрибутов элемента х, требующихся реализации множества. ОЕЕЕТЕ(Я,л) Модифицирующая операция, удаляюшая из заданного множества Я элемент, на юторый указывает х.(Обратите внимание, что в этой операции используется указатель на элемент, а не его ключевое значение.) М1н1мцм(Я) Запрос к полностью упорядоченному множеству 5, который возвращает указатель на элемент этого множества с наименьшим ключом.
МАХ1М12М(Я) Запрос к полностью упорядоченному множеству Я, который возвращает указатель на элемент этого множества с наибольшим ключом. ЯУССЕББОд(Я,л) Запрос к полностью упорядоченному множеству Я, который возвращает указатель на элемент множества Я, ключ которого является ближайшим соседом ключа элемента к и превышает его. Если же х — максимальный элемент множества Я, то возврашается значение н1е. Часть Ш.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
