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

Уровень 2

Уроаенб о

2 (0,1,1)



Уровень О

Дерево 7

Рис. 3.4. Числа, приписанные алгоритмом распознавания изоморфизма деревьев.

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

Следствие. Распознавание изоморфизма двух помеченных деревьев с п узлами, жтками которых служат целые числа между 1 и п, занимает время 0{п).

3.3. СОРТИРОВКА С ПОМОЩЬЮ СРАВНЕНИЙ

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



рядочивающий с помощью сравнений, должен делать по крайней мере О (п log п) сравнений на некоторой последовательности длины/г. Пусть надо упорядочить последовательность, состоящую из п различных элементов ai, а, . . . , а-п. Алгоритм, упорядочивающий с помощью сравнений, можно представить в виде дерева решений так, как описано в разд. 1.5. На рис. 1.18 изображено дерево решений, упорядочивающее последовательность а, Ь, с. Далее мы предполагаем, что если элемент а сравнивается с элементом b в некотором узле V дерева решений, то надо перейти к левому сыну узла v при а<:Ь и к правому - при db.

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

Лемма 3.1. Двоичное дерево высоты h содержит не более 2* листьев.

Доказательство. Элементарная индукция по h. Нужно лишь заметить, что двоичное дерево высоты h составлено из корня и самое большее двух поддеревьев, каждое высоты не более h-1. □

Теорема 3.4. Высота любого дерева решений, упорядочиваюш/гго последовательность из п различных элементов, не жньше log п\.

Доказательство. Так как результатом упорядочения последовательности из п элементов может быть любая из п\ перестановок входа, то в дереве решений должно быть по крайней мере п1 листьев. По лемме 3.1 высота такого дерева должна быть не меньше log п\. □

Следствие. В любом алгоритме, упорядочивающем с помощью сравнений, на упорядочение последовательности из п элементов тратится не меньше сп log п сравнений при некотором с>0 и достаточно большом п.

Доказательство. Заметим, что при п>\

п!>и(п-1)(п-2)...( J

г nix

так что log n!X7z/2)log(n/2)Xn/4)log п при п>4. □

По формуле Стирлинга точнее приближает п\ функция (п/е)", так что /г (log п-log е)=п log п-1,44/г служит хорошим приближением нижней границы числа сравнений, необходимых для упорядочения последовательности из п элементов.



3.4. СОРТДЕРЕВОМ -УПОРЯДОЧЕНИЕ С ПОМОЩЬЮ O(nlogn) СРАВНЕНИЙ

Так как любой сортирующий алгоритм, упорядочивающий с помощью сравнений, затрачивает по необходимости п log п сравнений для упорядочения хотя бы одной последовательности длины га, естественно спросить, существуют ли сортирующие алгоритмы, затрачивающие не более О (п log п) сравнений для упорядочения любой последовательности длины п. Один такой алгоритм мы уже видели - это сортировка слиянием из разд. 2.7. Другой алгоритм - Сортдеревом. Помимо того, что это полезный алгоритм упорядочения, в нем используется интересная структура данных, которая находит и другие приложения.

Сортдеревом лучше всего понять в терминах двоичного дерева вроде изображенного на рис. 3.5, у которого каждый лист имеет глубину d или d-1. Узлы дерева помечаются элементами последовательности, которую хотят упорядочить. Затем Сортдеревом меняет размещение этих элементов на дереве до тех пор, пока элемент, соответствующий произвольному узлу, станет не меньше элементов, соответствующих его сыновьям. Такое помеченное дерево мы будем называть сортирующим.

Пример 3.3. На рис. 3.5 изображено сортирующее дерево. Заметим, что последовательность элементов, лежащих на пути из любого листа в корень, линейно упорядочена и наибольший элемент в поддереве всегда соответствует его корню. □

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

Удобной структурой данных для сортирующего дерева служит такой массив А, что Л[1] - элемент в корне, а Al2i] и A[2i+l] --


Рис. 3.5. Сортирующее дерево.





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.0021