Алгоритмы - построение и анализ (1021735), страница 46
Текст из файла (страница 46)
Покажите, как выполнить сортировку этого массива за время О (и). (Порядок сортировки в этой задаче определяется обычным алфавитным порядюм; например, а < аЬ < Ь.) 8-4. Кувшины для воды Предположим, имеется и красных и и синих кувшинов для воды, которые различаются формой и объемом. Все красные кувшины могут вместить разное количество воды; то же относится и к синим кувшинам. Кроме того, каждому красному кувшину соответствует синий кувшин того же объема и наоборот. Задача заключается в том, чтобы разбить кувшины на пары, в каждой из юторых будут красный и синий кувшин одинакового обьема.
Для этого можно использовать такую операцию: сформировать пару кувшинов, в которых один будет синим, а второй — красным, наполнить красный Глава 8. Сортировка за линейное время 237 кувшин водой, а затем перелить ее в синий кувшин. Эта операция позволит узнать, какой из кувшинов больше или является ли их объем одинаковым.
Предположим, что для выполнения такой операции требуется одна единица времени. Необходимо сформулировать алгоритм, в котором для разбиения кувшинов на пары производилось бы минимальное количество сравнений. Напомним, что непосредственно сравнивать два красных или два синих кувшина нельзя. а) Опишите детерминистический алгоритм, в котором разбиение кувшинов на пары производилось бы с помощью 9 (пз] сравнений.
б) Докажите, что нижняя граница количества сравнений, которые должен выполнить алгоритм, предназначенный для решения этой задачи, равна Й(п 18 п). в) Разработайте рандомнзированный алгоритм, математическое ожидание количества сравнений в котором было бы равно О (п18п), и докажите корректность этой границы. Чему равно количество сравнений в этом алгоритме в наихудшем случае? 8-5.
Сортировка в среднем Предположим, что вместо сортировки массива нам нужно, чтобы его элементы возрастали в среднем. Точнее говоря, п-элементный массив А называется )сотсортировааньим, если для всех г = 1,2,...,п — )с выполняется такое соотношение: А [?] 2„А [Я а) Что из себя представляет 1-отсортированный массив? б) Приведите пример перестановки чисел 1, 2, ..., 10, являющейся 2-отсортированной, но ае отсортированной. в) Докажите, что п-элементный массив К-отсортировав тогда и только тогда, когда для всех г = 1,2,., и — /с справедливо соотношение А [1] ( А [1 + 1с].
г) Разработайте алгоритм, который выполняет й-сортировку и-элементного массива за время О (и 18 (и/й)). Можно также найти нижнюю границу для времени„необходимого для получения Й-отсортированного массива, если Й вЂ” константа. д) Покажите, что й-сортировку массива длины п можно выполнить за время О (п 18 lс). (Указание: воспользуйтесь решением упражнения 6.5-8.) Часть!1. Сортировка и порядковая статистика 238 е) Покажите, что если й — константа, то для й-сортировки и-элеменгного массива потребуется время П (п18п).
(Указание: воспользуйтесь решением предыдущего задания вместе с нижней границей для алгоритмов сортировки сравнением.) 8-6. Нижняя граница для объединения отсортированных списков Часто возникает задача объединения двух отсортированных списков. Эта процедура используется в качестве подпрограммы в процедуре МЕККЕ БОКт; она описана в разделе 2.3.1, где получила имя МЕКСЕ. В настоящей задаче мы покажем, что для количества сравнений, необходимых для объединения двух и-элементных отсортированных списков в наихудшем случае, существует нижняя граница, равная 2и — 1 сравнениям. Сначала с помощью дерева решений покажем, что нижняя граница количества сравнений равна 2п — о (и).
а) Покажите, что всего имеется (~„") способов разбиения 2п чисел на два отсортированных списка, в каждом из которых и чисел. б) Покажите с помощью дерева решений, что в любом алгоритме, корректно объединяющем два отсортированных списка, выполняется не менее 2и — о (и) сравнений. Теперь мы докажем наличие несколько более точной границы 2п — 1. в) Покажите, что если два элемента, которые в объединенном списке будут расположены последовательно один за другим, принадлежат разным подлежащим обьединению спискам, то в ходе объединения эти элементы обязательно придется сравнить. г) С помощью ответа на предыдущий пункт задачи покажите, что нижняя граница для количества сравнений, которые производятся прн объединении двух отсортированных списков, равна 2и — 1.
Заключительные замечания Использовать модель дерева решений при изучении алгоритмов сортировки сравнением впервые предложили Форд (гогд) и Джонсон (1о)шзоп) 194). В томе Искусства лрогральннрования Кнута (Кпш)з), посвященном сортировке [185), описываются различные разновидности задачи сортировки, включая приведенную здесь теоретико-информационную нижнюю границу для сложности сортировки.
Полное исследование нижних границ сортировки с помощью обобщений модели дерева решений было проведено Бен-Ором (Вел-Ог) 136). Согласно Кнуту, сортировка подсчетом впервые была предложена Севардом (Н.Н. Беюап1) в 1954 году; ему также принадлежит идея объединения сортировки Глава 8. Сортировка за линейное время 239 подсчетом и поразрядной сортировки. Оказывается, что поразрядная сортировка, начинающаяся с самой младшей значащей цифры, — по сути "народный" алгоритм, широко применявшийся операторами механических машин, предназначенных для сортировки перфокарт.
Как утверждает Кнут, первая ссылка на этот метод появилась в документе, составленном Комри (ЬЗ. Сошпе) и опубликованном в 1929 году, где описывается счетно-перфорационное оборудование. Карманная сортировка используется с 1956 года, с того времени, когда Исаак (ЕЗ. 1заас) и Синглтон (К.С. 8!пй!е!оп) предложили основную идею этого метода.
Мунро (Мишо) и Раман (Кашен) [229] предложили устойчивый алгоритм сортировки, который в наихудшем случае выполняет О (п1+') сравнений, где 0 < < в < 1 — произвольная константа. Несмотря на то, что в алгоритмах, время выполнения которых равно О (и 18 п), выполняется меньше сравнений, в алгоритме Мунро н Рамана данные перемещаются О (и) раз, и он выполняет сортировку на месте. Случай сортировки п 6-битовых чисел за время о (п1к и) рассматривался многими исследователями. Было получено несколько положительных результатов, в каждом из которых незначительно менялись предположения о вычислительной модели, а также накладываемые на алгоритм ограничения.
Во всех случаях предполагалось, что память компьютера разделена на адресуемые 6-битовые слова. Фредман (РгесЬпап) и Виллард (9У!1!агд) [99] первыми предложили использовать дерево слияний (Гпз!оп !гее) и выполнять с его помощью сортировку и целых чисел за время О (и 1к и/18!к п). Впоследствии эта граница была улучшена Андерссоном (Апдегззоп) [16] до О (пайп). В этих алгоритмах применяется операция умножения, а также некоторые предварительно вычисляемые константы. Андерссон, Хейгерап (Найегпр), Нильсон (!%!заел) и Раман [17] показали, как выполнить сортировку п чисел за время О (и 1к 1к п), не используя при этом умножение, однако этот метод требует дополнительной памяти, обьем которой увеличивается с ростом и.
С помощью мультипликативного хеширования объем этого пространства можно уменьшить до величины О (и), но при этом граница для наихудшего случая О (п18!ко) становится границей для математического ожидания времени работы. Обобщив экспоненциальные деревья поиска, Андерссон [16] и Торуп (Т!зогцр) [297] сформулировали алгоритм сортировки, выполняющийся в течение времени О (и (18!ко) ). В этом алгоритме не используется ни умножение, нн рандомизация, а обьем необходимой дополнительной памяти линейно зависит от количества элементов.
Дополнив эти методы новыми идеями, Хан (Нап) [137] улучшил границу времени работы до О (п 18 18 и 18 18 18 и). Несмотря на то, что упомянутые алгоритмы стали важным теоретическим достижением, все они чрезвычайно сложные, и в данный момент представляется маловероятным, чтобы они могли практически составить конкуренцию существующим алгоритмам сортировки. ГЛАВА 9 Медианы и порядковые статистики Будем называты-й порядковой статистикой (огбег ьтабзбс) множества, состоящего из и элементов, (-й элемент в порядке возрастания.
Например, минимум такого множества — это первая порядковая статистика (г = 1), а его максимум— это и-я порядковая статистика (г = п). Медиана (шеб(ап) неформально обозначает середину множества. Если и нечетное, то медиана единственная, и ее индекс равен ю' = (и + 1)/2; если же п четное, то медианы две, и их индексы равны г = п/2 и г = и/2+ 1. Таким образом, независимо от четности и, медианы располагаются при г = '1(п + 1)/2! (нижняя медиана (!ожег шейап)) и г = ! (и + 1)/21 (верхняя медияия (иррег тейап)). Однако в этой книге для простоты используется выражение "медиана", которое относится к нижней медиане.
Данная глава посвящена проблеме выбора г-й порядковой статистики в множестве, состоящем из п различных чисел. Для удобства предположим, что все числа в множестве различны, хотя почти все, что мы будем делать, обобщается на случай, когда некоторые значения в множестве повторяются. Формально задачу выбора (зе(есбоп ргоЫеш) можно определить следующим образом.
Вход: множество А, состоящее из и (различных) чисел, и число 1 < г < и. Выход: элемент к е А, превышающий по величине ровно г — 1 других элементов множества А. Задачу выбора можно решить за время О (п!кп). Для этого достаточно выполнить сортировку элементов с помощью пирамидальной сортировки или сортировки слиянием, а затем просто извлечь элемент выходного массива с индексом з. Однако есть и более быстрые алгоритмы. В разделе 9.1 рассматривается задача о выборе минимального и максимального элементов множества. Больший интерес представляет общая задача выбора, Глава 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
