1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 20
Текст из файла (страница 20)
пусть А,— первая цепочка в списке ОЧЕРЕДЬ; 7. переместить А, из списка ОЧЕРЕДЬ в черпак Цагг) епа(; 8. 1ог 1Е НЕПУСТОЙ[1) до Ьей(п 9. присоединить содержимое списка Щ1] к концу списка ОЧЕРЕДЬ; 1О. сделать список 1~[11 пустым епй епо' епп х) С формальной точки зрения можно присоединять лишь к концу очереди, но конкатенация к началу не должна вызывать никаких трудностей. Более аффективным приемом здесь был бы такой: выбрать цепочки А; из списка ДЛИНА[О сначала в строке 6, а затем из списка ОЧЕРЕДЬ и совсем не устраивать конкатенации списков ДЛИНА(т) и ОЧЕРЕДЬ.
Рис. Зхь Лексикографическая сортировка цепочек разной длины. ства писать в списках сами цепочки, а не указатели иа них. Однако надо помнить, что в очередях хранятся эти указатели, а не сами цепочки. В части 1 алгоритма 3.2 формируется пара (1, а) из первой цепочки, пары (1„Ь), (2, а), (3„Ь) из второй и (1, а), (2, Ь), (3, с) из третьей. Упорядоченный список этих пар выглядит так: (1, а) (1, а) (1, Ь) (2, а) (2, Ь) (3, Ь)(3, с) Просматривая его слева направо, заключаем, что НЕПУСТОЙ [Ц=а, Ь; НЕПУСТОЙ[2[=а, Ь; НЕПУСТОЙ 131= Ь, с 1йв З.к ЦИФРОВАЯ СОРТИРОВКА цеенчня ЦАнаме Рнс.
3.3. Структура данных нлн Веночек. В части 2 алгоритма 3.2 вычисляем 1,=1, 1,=3 и 1,=3. Следовательно, ДЛИНА[!]=а, список ДЛИНА[2] пуст и ДЛИНА[3]=ЬаЬ, аЬс. Поэтому часть 3 начинаем с того, что полагаем ОЧЕРЕДЬ= Ьад, аЬс, и затем располагаем эти цепочки по их третьей компоненте. Равенство НЕПУСТОЙ[3]=Ь, с гарантирует, что при построении упорядоченного списка в соответствии со строками 8 — 1О рис. 3.2 не обязательно присоединить 1е[а! к концу списка ОЧЕРЕДЬ. Таким образом, после первого прохождения цикла в строках 3 — !О рис. 3.2 ОЧЕРЕДЬ=ЬЦЬ, аЬс. При втором прохождении ОЧЕРЕДЬ не меняется, так как список ДЛИНА[2] пуст, а упорядочение по второй компоненте не изменяет порядок.
При третьем прохождении мы, согласно строке 4, получаем ОЧЕРЕДЬ=а, ЬаЬ, аЬс, Упорядочение по первой компоненте дает ОЧЕРЕДЬ=а, аЬс, ЬаЬ; получили правильный порядок. Заметим, что при третьем прохождении список а1[с] становится пустым, а поскольку с не входит в список НЕПУСТОЙ[!], не нужно присоединять 9с] к концу списка ОЧЕРЕДЬ. [] Теорема 3.2.
Алгоритм 3.2 упорядочивает свой вход за время н 0(1н+т), где 1А=Х1И га-3 До к а з а тел ь с т в о. Простая нндукция по числу прохождений внешнего цикла в программе на рис. 3.2 показывает, что после 1 прохождений список ОЧЕРЕДЬ содержит цепочки длины, ие меньшей 1,„— 1+1, и они расположены в соответствии с их компонентами с номерами от 1 „„— 1+1 до 1,„. Поэтому рассматриваемый алгоритм лексикографически упорядочивает свой вход.
101 гл а. соптииовкл и пооядковын стлтистики Что касается затрачиваемого временн, то в части 1 расходуется время 0(1е) на образование списка пар н 0(т+1а) на его упорядочение. Аналогично часть 2 занимает не более 0((е) времени. Теперь исследуем часть 3 н программу на рнс. 3.2. Пусть и!— число цепочек, имеющих с-е компоненты. Пусть т; — число различных символов, появляющихся в г-х компонентах цепочек (т. е. т! — длина списка НЕПУСТОЙ(!)). Рассмотрим фиксированное значение 1 в строке 3 рнс, 3.2. Цикл в строках 5 — 7 занимает 0(п,) времени, а в строках 8 — 10 — 0(т,) времени. Шаг 4 выполняется за постоянное время, так что одно прохождение цикла в строках 3 — 10 занимает 0(тхтп!) времени.
Таким образом, весь цикл занимает ! 0 ~ (т,+и) времени. Так как ! шах ! мах ~а тся (а н ~ па~(а, г=! с=! то строки 3 — ! О выполняются за время 0((а). Теперь, учитывая, что на строку 1 тратится постоянное время, а на строку 2 время 0(т), получаем нужный результат. () Приведем пример, когда упорядочение возникает прн разработ- ке алгоритма. Пример 3.2. Два дерева называются изоморфными, если можно отобразить одно нз ннх в другое, изменив порядок сыновей его уз- лов. Рассмотрим задачу распознавания изоморфизма двух данных деревьев Т, н Т,. Следующий алгоритм делает это за время, пропор- цнональное числу узлов. Этот алгоритм приписывает целые числа узлам двух данных деревьев, начиная с узлов уровня О н двигаясь вверх до корней, так что деревья нзоморфны тогда н только тогда, когда нх корням приписано одно н то же число.
Алгоритм работает так. 1. Приписать число О всем листьям деревьев Т, н Т,. 2, (Индукцня,) Предположим, что целые числа уже приписаны всем узлам, находящимся в деревьях Т, н Т, на уровне ! — 1. Пусть Š— список узлов .уровня ! — 1 в дереве Т„ расположенных в порядке неубывання приписанных нм чисел, а Ьа — соотвегствующнй список для Т,'). 3. Приписать нелнстьям уровня ! в дереве Т, кортеж целых чисел следующим образом; просмотреть список 1.! слева направо н для каждого узла и нз Ь! взять число, ему приписанное, в !) Надо уволиться, что, проходя дерево в прямом порядке, можно приписать номера уровней аа 0(п) шагов.
° ва 3.2. циФРОВАя ООРтиРОВкА качестве очередной компоненты кортежа, который ставится в соответствии отцу узла п. После выполнения этого шага каждому нелисту 1п уровня 1 в дереве Т, будет поставлен в СООтВЕтСтВИЕ КОртЕж (Юы 1м ..., )а), ГдЕ 1И Ю'а...., ЕЬ— целые числа, приписанные сыновьям узла 1п и расположенные в порядке неубывання. Обозначим через 5, последовательность кортежей, построенных для узлов уровня 1 в дереве Т,. 4. Повторить шаг 3 для Т,; пусть 5, — последовательность кортежей, построенных для узлов уровня 1 в дереве Т,. б.
Упорядочить 5, и 5, с помощью алгоритма 3.2, Пусть соответственно 5; и 5; — упорядоченные последовательности кортежей. 6. Если 5; и 5; не совпадают, то остановиться; в этом случае исходные деревья не изоморфны. В противном случае приписать число 1 тем узлам уровня 1 в дереве Т„которые представлены первым кортежем в 5;, число 2 — вторым отличающимся кортежем'), и т. д.
Так как эти целые числа приписаны узлам уровня 1 в дереве Т„построить список Е, из узлов, которым таким способом приписаны числа, Добавить к началу списка Е, все листья дерева Т„расположенные на уровне й Пусть Т.а — соответствующий список узлов дерева Т,. Эти два списка теперь можно использовать для приписывания кортежей узлам уровня 1+1 с помощью процедуры иа шаге 3. 7. Если корням деревьев Т, и Т, приписано одно и то же число, то Т, и Т, изоморфны. На рис. 3.4 иллюстрируется приписывание чисел и кортежей узлам двух изоморфных деревьев.
Теорема 3.3. Изоморфизм двух деревьев с и узлами можно распсзнать за время 0 (и). Д о к а з а те л ь с т в о. Теорема следует из формализации алгоритма, изложенного в примере 3.2. Доказательство корректности алгоритма мы опускаем. Время работы можно оценить, если заметить, что приписывание целых чисел узлам уровня 1, отличным от листьев, занимает время, пропорциональное числу узлов уровня 1 — 1. Суммирование по всем уровням дает время 0(п). Работа по приписыванию чисел листьям также пропорциональна п, и, таким образом, весь алгоритм занимает время 0 (л), С) 17омеченным называется дерево, в котором узлам приписаны метки. Допустим, что метками узлов служат целые числа между 1 ') Имеется в виду не кортеж, стоящий на 2-м месте в списке 5т (который может совпасть с кортежем, стоящим яа )-и месте), а тот кортеж, который окажется на 2-и месте после вычеркивания иа 5т всех повторений.— Прим.
ред. 103 ГЛ. 3. СОРТИРОВКА И ПОРЯДКОВЫЕ СТАТИСТИКИ Уров Уроеогв 2 Уроеевв 1 агапово Т, Уроееав Урвоеед 1 Урпмгв о ,аорвао ?а Рис. ЗЛ. Числа, приписанные алгоритмом распознавания изоморфизма деревьев. и и. Тогда изоморфизм двух помеченных деревьев можно распознать за линейное время, если включить метку каждого узла в качестве первой компоненты кортежа, приписываемого этому узлу изложенным выше алгоритмом. Таким образом, справедливо Следствие. Распознавание изоморфизма двух помеченных деревьев с п узлами, метками которых служат целые числа между 1 и п, занимает время 0(п), 3.3.
СОРТИРОВКА С ПОМОЩЬЮ СРАВНЕНИЙ Здесь мы изучим задачу упорядочения последовательности из и элементов, взятых из линейно упорядоченного множества 5, о структуре которых ничего не известно. Информацию об этой последовательности можно получить только с помощью операции сравнения двух элементов. Сначала мы покажем, что любой алгоритм, упо- 3.3. ООРтиРОВкх с помощью сРАВнений рядочивающий с помощью сравнений, должен делать по крайней мере 0(п 1оя и) сравнений на некоторой последовательности длины и.
Пусть надо упорядочить последовательность, состоящую из и различных элементов а„а„..., а . Алгоритм, упорядочивающий с помощью сравнений, можно представить в виде дерева решений так, как описано в равд. 1.5. На рис. 1.18 изображено дерево решений, упорядочивающее последовательность а, Ь, с. Далее мы предполагаем, что если элемент а сравнивается с элементом Ь в некотором узле о дерева решений, то надо перейти к левому сыну узла о при а(Ь и к правому — при агЬ.
Как правило, алгоритмы сортировки, в которых для разветвления используются сравнения, ограничиваются сравнением за один раз двух входных элементов. В самом деле, алгоритм, который работает на произвольном линейно упорядоченном множестве, не может никак преобразовать входные данные, поскольку при самой общей постановке задачи операции иад данными "не имеют смысла'*. Так или иначе, мы докажем сильный результат о высоте любого дерева решений, упорядочивающего последовательность из и элементов. Лемма 3.!. Двоичное дерево высоты Ь содержит не более 2" листьев.
Д о к а з а тел ь с т в о. Элементарная индукция по 6. Нужно лишь заметить, что двоичное дерево высоты Ь составлено из корня и самое большее двух поддеревьев, каждое высоты не более /3 — 1. П Теорема 3.4. Высота любого дерева решений, упорядочивающего последовательность из и различных элементов, не меньше !Оя и!. До к а з а те л ь от в о. Так как результатом упорядочения последовательности из и элементов может быть любая из и! перестановок входа, то в дереве решений должно быть по крайней мере п1 листьев. По лемме 3.1 высота такого дерева должна быть не меньше 1оя и!. П Следствие.
В любом алгоритме, упорядочивающем с помощью сравнений, на упорядочение последовательности из и элементов тратится не меньше сп 1оя и сравнений при некотором с)0 и достаточно большом и. Доказательство. Заметим, что при п)! — — ТН-®' так что !Оя п)=э(п/2)!Од(п/2))(п/4)!Од и при п)4. () По формуле Стирлинга точнее приближает и! функция (и/е)", так что и (!Оя и — !оя е) =и 1оя и — 1,44п служит хорошим приближением нижней границы числа сравнений, необходимых для упорядочения последовательности из и элементов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
