Главная Промышленная автоматика.

Замечания по литературе

Дополнительную информацию о структурах данных и их реализации можно найти у Кнута [1968] и Стоуна [1972]. Книга Пратта [1975] содержит описание реализации рекурсии в языках, подобных Алголу. Берж [1958] и Харари [1969J излагают теорию графов. Кнут [1968] дает информацию о деревьях и их прохождении. Дальнейшие сведения об алгоритмах прохождения деревьев можно найти у Беркхарда [1973].

Оптимальность алгоритма 2.3 (для нахождения максимума и минимума) показал Поль [1972]. Алгоритм сложности 0{п) для умножения целых чисел (разд. 2.6) приведен в работе Карацубы, Офмана [1962J. Виноград [1973] рассматривает подобные приемы ускорения с более общей точки зрения.

Понятие динамического программирования популяризировал Беллман [1957], а алгоритм 2.5 - известное приложение этого понятия опубликованное Год-боулом [1973] и Мураокой, Кукком [1973]. Приложением динамического программирования к распознаванию принадлежности бесконтекстному языку (упр. 2.34) независимо друг от друга занимались Касами [1965], Янгер [1967] и Кок. В работе Вагнера, Фишера [1974] содержится решение упр. 2.35.

Дальнейшую информацию о решении рекуррентных уравнений см. Лю 11968] или Слоун £1973].



СОРТИРОВКА

и ПОРЯДКОВЫЕ СТАТИСТИКИ

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

Сортировка - практически важная и теоретически интересная задача. Поскольку сортировка больших объемов данных составляет значительную часть коммерческой обработки данных, эффективные алгоритмы для сортировки важны и с экономической точки зрения. Что же касается разработки алгоритмов, то даже здесь процесс сортировки последовательности элементов очень важен - он является существенной частью многих алгоритмов.

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

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



3.1. ЗАДАЧА СОРТИРОВКИ

Определение. Частичным порядком на множестве S называется такое двухместное отношение R, что для любых а, b и с т S

1) aRa (R рефлексивно),

2) из aRb и bRc следует aRc (R транзитивно),

3) из aRb и bRa следует а=Ь (R антисимметрично).

Примеры частичных порядков - отношение на множестве целых чисел и отношение (включение множеств).

Линейным, или полным, порядком на множестве S называется такой частичный порядок R на S, что для любых двух элементов а, Ь выполняется либо aRb, либо bRa.

Отношение < на множестве целых чисел является линейным порядком 1), а включение множеств s нет.

Задачу сортировки можно сформулировать так: дана последовательность из п элементов Oi, Оа, • • • , Оп. выбранных из множества, на котором задан линейный порядок (обычно мы будем обозначать его О. Требуется найти перестановку я этих п элементов, которая отобразит данную последовательность в неубывающую последовательность a„(j), a„,2„ . . . , а„(„„ т. е. a„(,,<a;„,i-+i, при 1</<п. Как правило, мы будем вырабатывать саму упорядоченную последовательность, а не упорядочивающую перестановку п.

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

Внутренняя сортировка важна как для разработки алгоритмов, так и для коммерческих приложений. В тех случаях, когда сортировка возникает как часть другого алгоритма, число сортируемых элементов обычно мало, и они помещаются в оперативную память. Тем не менее мы будем предполагать, что элементов, подлежащих сортировке, довольно много. Если же надо упорядочить только горстку элементов, то гораздо выгоднее простая стратегия вроде "сортировки взбалтыванием" со сложностью 0{п) (упр. 3.5).

Известно много алгоритмов сортировки. Мы не пытаемся охватить даже все те из них, которые считаются важными; скорее мы

1) Если < - линейный порядок, то пишут а<й, когда а<й и аЬ (как и следовало ожидать). Кроме того, Ь>а означает то же, что и о<6, а Ьа - тоже, что и о<й.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 [27] 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0022