1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 18

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 18)

Для вычисления тм примените динамическое программироваиие. "2.33. Пусть х и у — цепочки символов и некоторого алфавита. Рассмотрите операции удаления символа изх, вставки символа в х и замены символа в х другим символом. Опишите алгоритм нахождения минимального числа таких операций, необходимых для преобразования х в у. гл.

з. рдзплноткд веьвнктиниых длгоритмов Замечания пе литературе )[ополннтельную информацию о структурах данных н вх реэлнзэцкн можно найти у Кнута [!968[ н Стоунз [1972[. Книга Прэттв [1976[ содержнт опнсэнне реализации рекурсии в языках, подобных Алголу. Берж [!968[ н Хнрврн [1969[ нэлэгвют.теорню графов. Кнут [1968) дает ннформзцню о деревьях н нх прохожденнн. Лэльнейшне сведения об алгоритмах прохаждення деревьев можно нэйтн у Беркхэрдэ [1973).

Оптнмэльность алгоритма 23 (для нахождения максимума н мнннмумв) покэзэл Поль [1972!. Алгоритм сложности 0(л™) для умноження целых чисел (рэзд. 2.6) приведен в работе Кэрвцубы, Офмзнв [1962[. Виноград [1973) рве. смэтрнввет подобные приемы ускорения с более общей точкн зрения. Понятне дннэмнческого прогрэммнроввння популярнзнроввл Беллмен [1957[, э алгоритм 2.6 — известное прнложенне этого понятия опубликованное Годбоулом [1973) в Мураокой, Кукком [!973). Прнложеннем дннэмнческого прогрвммнровэвня к рэспоэнэвэнню прннвдлежностн бесконтекстному языку (упр.

2,34) неэввнснмо друг от друга эвннмэлнсь Кэсэмн [1966[, Янгер [1967[ н Кок. В рэботе Вагнера, Фншерз [1974) содержнтся решение упр.2.35. Лэльнейшую ннформвцню о решеннн рекуррентвых урэвненнй см. Лю [1968[ влн Слоун [1973[. з СОРТИРОВКА И ПОРЯДКОВЫЕ СТАТИСТИКИ В этой главе изучаются две взаимосвязанные задачи — сортировка последовательности элементов н выбор й-го наименьшего элемента последовательности.

Под сортировкой последовательности мы подразумеваем переупорядочение ее элементов в такую последовательность, где все элементы расположены в порядке невозрастания илн неубывания. Можно найти й-й наименьший элемент последовательности, расположив ее элементы в порядке неубывання и выбрав из полученной последовательности й-й элемент. Однако мы увидим, что выбрать й-й наименьший элемент можно быстрее. Сортировка — практически важная и теоретически интересная задача.

Поскольку сортировка больших объемов данных составляет значительную часть коммерческой обработки данных, эффективные алгоритмы для сортировки важны и с экономической точки зрения. Что же касается разработки алгоритмов, то даже здесь процесс сортировки последовательности элементов очень важен — он является существенной частью многих алгоритмов. В данной главе рассматриваются два класса сортирующих алгоритмов. Первый основан на использовании структуры сортируемых элементов. Например, если сортируемые элементы представлены числамн от 0 до и — 1, то можно упорядочить последовательность из и элементов за время 0 (и+ги), а если словами в некотором алфавите, то за время, пропорциональное сумме длин этих слов. Второй класс алгоритмов не предполагает у сортируемых элементов никакой структуры.

Основная операция — сравнение двух элементов. В алгоритмах этого типа, как мы увидим, для сортировки последовательности, состоящей нз и элементов, требуется по крайней мере и !оя и сравнений. Мы дадим два сортирующих алгоритма сложности Ос(и 1од и), а именно Сортдеревом со сложностью Ос(и 1оя и) в худшем случае и Быстрсорт со средней сложностью Ос(и 1од и). гл з. сортироикл и понядковыв стдтистики ЗЛ. ЗАДАЧА СОРТИРОВКИ Определение. Частичным порядком на множестве Я называется такое двухместное отношение )т, что для любых а, Ь и с из 3 1) а)та ()т рефлексивно), 2) из а<с Ь и Ьйс следует а)тс Я транзитивно), 3) из а)тЬ и Ыа следует а=Ь ()т антисимметрично).

Примеры частичных порядков — отношение ~ (на множестве целых чисел и отношение с: — (включеиие множеств). Линейным, илн полным, порядком на множестве Я называется такой частичный порядок )т на Я, что для любых двух элементов а, Ь выполняется либо аЯЬ, либо Ь)та. Отношение ( на множестве целых чисел является линейным порядком '), а включение множеств и нет. Задачу сортировки можно сформулировать так: дана последовательность из и элементов а„а„..., а„, выбранных из множества, на котором задан линейный порядок (обычио мы будем обозначать его (). Требуется найти перестановку и этих и элементов, которая отобразит данную последовательность в неубывающую последовательность ан<п ан<е< ° ° ан<н< т е ан<о((а~<<то при 1<ты<(п, Как правило, мы будем вырабатывать саму упорядоченную последовательность, а не упорядочиваккцую перестановку и.

Методы сортировки классифицируются на внутренние (когда данные размещаются в памяти с произвольным доступом) и внешнив (когда данные размещаются преимущественно вне памяти с произвольным доступом). Внешняя сортировка составляет часть таких приложений, как обработка расчетов, при которой в работу вовлекается гораздо больше элементов, чем можно сразу запомнить в оперативной памяти. Поэтому методы внешней сортировки, применимые к данным, находящимся на внешних устройствах памяти (таких, как диски или магнитные ленты), имеют огромное коммерческое значение. Внутренняя сортировка важна как для разработки алгоритмов, так и для коммерческих приложений. В тех случаях, когда сортировка возникает как часть другого алгоритма, число сортируемых элементов обычно мало, н они помещаются в оперативную память. Тем не менее мы будем предполагать, что элементов, подлежащих сортировке, довольно много.

Если же надо упорядочить только горстку элементов, то гораздо выгоднее простая стратегия вроде "сортировки взбалтываниемн со сложностью 0(пз) (упр. 3.5). Известно много алгоритмов сортировки. Мы не пытаемся охватить даже все те из иих, которые считаются важными; скорее мы ') Если а — линейный порядок, то пишут а<Ь, когда а~Ь и пеьЬ (кзк и сзедозззо ожидзть). Кроне того, Ь)а ознзчзет то же, что и а(Ь, з Ь-ьа — тоже, что н а~Ь. Х2 ЦИФРОВАЯ СОРТИРОВКА ограничимся методами, оказавшимися полезными в разработке алгоритмов.

Сначала будет рассмотрен случай, когда элементы, подлежащие сортировке, представлены целыми числами или (что почти эквивалентно) словами в конечном алфавите. В этой ситуации мы увидим, что сортировку можно выполнить за линейное время. Затем изучим задачу сортировки, когда специальные свойства чисел или слов не используются и приходится строить разветвления в программе только на основе результатов сравнений сортируемых элементов. При этих условиях необходимо 0(л )оя л) сравнений; это же количество сравнений достаточно для упорядочения последовательности из л элементов.

3.2. ЦИФРОВАЯ СОРТИРОВНА Начнем с последовательности целых чисел а„а„..., а„, заключенных между О и т — 1. Если т не слишком велико, ее можно упорядочить следующим образом. 1. Организуем т пустых очередей по одной для каждого целого числа от О до т — 1.

Каждую такую очередь назовем черпаком. 2. Просмотрим последовательность а„а„..., а„слева направо, помещая элемент а, в очередь с номером а». 3. Сцепим эти очереди (содержимое (»+!)-й очереди приписывается к концу»'-й очереди) и получим в результате упорядо. ченную последовательность. Так как любой элемент можно вставить в»-ю очередь за постоянное время, то л элементов можно вставить в очереди за время 0 (и).

Конкатенация (сцепление) т очередей требует времени 0(т). Если т есть 0(л), то этот алгоритм сортирует и целых чисел за время 0(п). Назовем его сортировкой еычерпыаанием. Процедуру сортировки вычерпыванием можно обобщить так, чтобы она упорядочивала последовательность кортежей (т, е. спи.

сков) целых чисел в лексикографическом порядке. Пусть ( — линейный порядок на множестве 5. Лексикографическим порядком называется такое продолжение отношения ( на кортежи элементов из 5, при котором (з„з„..., ВР)((1„1„..., »,) означает, что выполнено одно из условий: 1) существует такое целое число 1, что з»(!» и для всех 1(! справедливо В,=»„ 2) р=»! и з»=!» при 1<»<р. Например, в словаре слова расположены в лексикографическом порядке, если рассматривать их как кортежи из букв (на буквах задан естественный алфавитный порядок). Сначала обобщим сортировку вычерпыванием на последовательности, состоящие из й-членных кортежей, компонентами которых ГЛ. 3.

СОРТИРОВКА И ПОРЯДКОВЫЕ СТАТИСТИКИ являются целые числа от О до т — 1. Сортировка осуществляется с помощью й прохождений по данной последовательности, на каждом из которых применяется сортировка вычерпыванием. Во время первого прохождения кортежи упорядочиваются по их л-м компонентам. Во время второго прохождения полученная последовательность упорядочивается по (й — 1)-м компонентам. При третьем последовательность, полученная после второго прохождения, упорядочивается по (й — 2)-м компонентам.и т. д. При й-м (последнем) прохождении последовательность, полученная после (к — 1)-го прохождения, упорядочивается по первым компонентам '). Теперь элементы последовательности расположены в лексико- графическом порядке. Дадим точное описание этого алгоритма.

Характеристики

Список файлов книги