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

ЦЕПОЧКЛ

ДАННЫЕ

Рис. 3.3. Структура данных для цепочек.

В части 2 алгоритма 3.2 вычисляем /i=l, /2=3 и /з=3. Следовательно, ДЛИНА! 1]=а, список ДЛИНА[2] пуст и ДЛИНА[3]=&а6, аЪс. Поэтому часть 3 начинаем с того, что полагаем ОЧЕРЕДЬ= ЬаЪ, аЬс, и затем располагаем эти цепочки по их третьей компоненте. Равенство НЕПУСТ0Й[3]=&, с гарантирует, что при построении упорядоченного списка в соответствии со строками 8-10 рис. 3.2 не обязательно присоединить Q[a] к концу списка ОЧЕРЕДЬ. Таким образом, после первого прохождения цикла в строках 3-10 рис. 3.2 ОЧЕРЕДЬ=ЬаЬ, аЬс.

При втором прохождении ОЧЕРЕДЬ не меняется, так как список ДЛИНА[2] пуст, а упорядочение по второй компоненте не изменяет порядок. При третьем прохождении мы, согласно строке 4, получаем ОЧЕРЕДЬ=а, bab, abc. Упорядочение по первой компоненте дает ОЧЕРЕДЬ=а, abc, bab; получили правильный порядок. Заметим, что при третьем прохождении список Q[c] становится пустым, а поскольку с не входит в список НЕПУСТОЙ! 1], не нужно присоединять Qlc] к концу списка ОЧЕРЕДЬ. □

Теорема 3.2. Алгоритм 3.2 упорядочивает свой вход за время

0(/*+т), где lJh-

Доказательство. Простая индукция по числу прохождений внешнего цикла в программе на рис. 3.2 показывает, что после / прохождений список ОЧЕРЕДЬ содержит цепочки длины, не меньшей 1-/+1, и они расположены в соответствии с их компонентами с номерами от -/+1 до /„а,. Поэтому рассматриваемый алгоритм лексикографически упорядочивает свой вход.



Что касается затрачиваемого времени, то в части 1 расходуется время 0{1*) на образование списка пар и 0(т+/*) на его упорядочение. Аналогично часть 2 занимает не более 0(1*) времени.

Теперь исследуем часть 3 и программу на рис. 3.2. Пусть п, - число цепочек, имеющих t-e компоненты. Пусть т,- - число различных символов, появляющихся в i-x компонентах цепочек (т. е. nii - длина списка НЕПУСТОЙ!/]).

Рассмотрим фиксированное значение / в строке 3 рис. 3.2. Цикл в строках 5-7 занимает 0(n,) времени, а в строках 8-10 - 0(m,) времени. Шаг 4 выполняется за постоянное время, так что одно прохождение цикла в строках 3-10 занимает ©(m-fn,) времени. Таким образом, весь цикл занимает

/max \

О 2 К + П,)

времени. Так как

2 m, < /* И 2 <

1=1 1=1

то строки 3-10 выполняются за время 0{1*). Теперь, учитывая, что на строку 1 тратится постоянное время, а на строку 2 время 0{т), получаем нужный результат. □

Приведем пример, когда упорядочение возникает при разработке алгоритма.

Пример 3.2. Два дерева называются изоморфными, если можно отобразить одно из них в другое, изменив порядок сыновей его узлов. Рассмотрим задачу распознавания изоморфизма двух данных деревьев Ti и Т. Следующий алгоритм делает это за время, пропорциональное числу узлов. Этот алгоритм приписывает целые числа узлам двух данных деревьев, начиная с узлов уровня О и двигаясь вверх до корней, так что деревья изоморфны тогда и только тогда, когда их корням приписано одно и то же число. Алгоритм работает так.

1. Приписать число О всем листьям деревьев и Та.

2. (Индукция.) Предположим, что целые числа уже приписаны всем узлам, находящимся в деревьях Ti и Та на уровне i-1. Пусть L - список узлов .уровня i-1 в дереве Ti, расположенных в порядке неубывания приписанных им чисел, а La - соответствующий список для T2).

3. Приписать нелистьям уровня i в дереве Ti кортеж целых чисел следующим образом: просмотреть список Li слева направо и для каждого узла и из L] взять число, ему приписанное, в

1) Надо убедиться, что, проходя дерево в прямом порядке, можно приписать номера уровней за 0{п) шагов.



качестве очередной компоненты кортежа, который ставится в соответствии отцу узла и. После выполнения этого шага каждому нелисту w уровня i в дереве будет поставлен в

соответствие кортеж (ij, I2.....г), где i, .....ih -

целые числа, приписанные сыновьям узла w и расположенные в порядке неубывания. Обозначим через 5i последовательность кортежей, построенных для узлов уровня i в дереве Tj,

4. Повторить шаг 3 для Т, пусть 5 2 - последовательность кортежей, построенных для узлов уровня i в дереве Га.

б. Упорядочить 5j и Sa с помощью алгоритма 3.2. Пусть соответственно 5i и 5а - упорядоченные последовательности кортежей.

6. Если 51 и Sa не совпадают, то остановиться; в этом случае исходные деревья не изоморфны. В противном случае приписать число 1 тем узлам уровня i в дереве Ти которые представлены первым кортежем в 5, число 2 - вторым отличающимся кортежем!), и т. д. Так как эти целые числа приписаны узлам уровня i в дереве Ti, построить список Li из узлов, которым таким способом приписаны числа. Добавить к началу списка Li все листья дерева Т расположенные на уровне i. Пусть La - соответствующий список узлов дерева Та. Эти два списка теперь можно использовать для приписывания кортежей узлам уровня г+1 с помощью процедуры на шаге 3.

7. Если корням деревьев Т и Га приписано одно и то же число,

то Ti и Га изоморфны. □

На рис. 3.4 иллюстрируется приписывание чисел и кортежей узлам двух изоморфных деревьев.

Теорема 3.3. Изоморфизм двух деревьев с п узлами можно распознать за время О (п).

Доказательство. Теорема следует из формализации алгоритма, изложенного в примере 3.2. Доказательство корректности алгоритма мы опускаем. Время работы можно оценить, если заметить, что приписывание целых чисел узлам уровня i, отличным от листьев, занимает время, пропорциональное числу узлов уровня i-1. Суммирование по всем уровням дает время 0{п). Работа по приписыванию чисел листьям также пропорциональна п, и, таким образом, весь алгоритм занимает время 0{п). □

Помеченным называется дерево, в котором узлам приписаны метки. Допустим, что метками узлов служат целые числа между 1

1) Имеется в виду не кортеж, стоящий на 2-м месте в списке Si (который может совпасть с кортежем, стоящим на 1-м месте), а тот кортеж, который окажется на 2-м месте после вычеркивания из Sl всех повторений.- Прим. ред.





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