1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 32
Текст из файла (страница 32)
Д о к а з а т е л ь с т в о. Пусть с — такая постоянная, что алгоритм 4.3 выполнит любую последовательность из и — ! операций ОБЪЕДИНИТЬ и и операций НАЙТИ не более чем за сп единиц времени. Выберем й:Р4с и вычислим 477=0 (й, 1, !). Построим Т'(я) с помощью последовательности операций ОБЪЕДИНИТЬ.
Так как можно вьшолнить ЧН длины й на каждом листе вложенного дерева Т(я), листья которого занимают более четверти узлов дерева Т'(я), то эта последовательность операций ОБЪЕДИНИТЬ и ЧН потратит более сп единиц времени; получили противоречие. П 6 А.
Апо, Дж. Хоппрофт, Дж. Упьппп 666 гл, е стрнктнры данных для задач с множнствдми 4.3. ПРИЛОЖЕНИЯ И ОБОБЩЕНИЯ АЛГОРИТМА ОБЪБДИНИТЬ вЂ” НАЙТИ Мы уже видели, как в задаче построения остовного дерева, описанной в примере 4.1, естественно возникает последовательность основных операций ОБЪЕДИНИТЬ и НАЙТИ. В этом разделе мы познакомимся с несколькими другими задачами, которые приводят к последовательностям операций ОБЪЕДИНИТЬ и НАЙТИ. В нашей первой задаче надо осуществить вычисления в свободном режиме, т. е. прочесть всю последовательность операций перед выдачей каких бы то ни было ответов.
Приложение 1. М)й)-задача в свободном режиме Даны два типа операций: ВСТАВИТЬ(1) и ИЗВЛЕЧЬ М1Н. Начнем с множества 5, вначале пустого. Каждый раз, когда встречается операции ВСТАВИТЬ(!), целое число ! помещается в 5. Каждый раз, когда выполняется операция ИЗВЛЕЧЬ М1Х, разыскивается и удаляется наименьший элемент в 5. Пусть и — такая последовательность операций ВСТАВИТЬ и ИЗВЛЕЧЬ М1Ы, что для каждого 1, 1<!(и, операция ВСТАВИТЬ(!) встречается не более одного раза. По данной последовательности о надо найти последовательность целых чисел, удаляемых операцией ИЗВЛЕЧЬ М1Ы. Задача решается в свободном режиме, поскольку предполагается, что вся последовательность о известна до того, как надо вычислить даже первый элемент выходной последовательности.
М1)ч)-задачу в свободном режиме можно решить следующим методом. Пусть 4 — число операций ИЗВЛЕЧЬ М!Х в и. Можно записать и в виде о,Ео,Ео,Е...паЕа +и где каждая подпоследовательность пь 1(!(4+1, состоит только из операций ВСТАВИТЬ, !ог ! 1 ппП! а 4!о Ьей!п — НАЙТИ(!); П !(й !Ьеп Ьед!п рг!п1 ! "удаляется 1-й операцией ИЗВЛЕс!Ь..М1Ы"; ОБЪЕДИНИТЬ!1, СЛЕДИ, СЛЕД[!)); СЛ ЕД [ПРЕД [111 — СЛ ЕДИ; ПРЕД[СЛЕД[!)1 — ПРЕД[!) Евс! епд Рис. 4.23.
Программа ддн решенин М!Ы-задачи в свободном режиме. 462 ьа пгиложвния и ововщвния ллгогитмл овъвдинить — нлпти а Е обозначает операцию ИЗВЛЕЧЬ М1Ы. Промоделируем о с помощью алгоритма 4.3. Начальная последовательность множеств для работы алгоритма объединения строится так: если в последовательности о; встречается операция ВСТАВИТЬ(!), то считаем, что множество с именем 1, 1<!<я+1, содержит элемент 4. Для того чтобы для тех значений 1, для которых существует множество с именем 1, образовать дважды связанный упорядоченный список, пользуемся двумя массивами ПРЕД и СЛЕД.
Вначале ПРЕД[!)= =-! — 1 для 1<!<!4+1 и СЛЕД[!)=!+1 для О<!<!4. Затем выполняется программа, приведенная на рис. 4.23. Легко видеть, что время выполнения этой программы ограничено временем работы алгоритма объединения множеств. Следовательно, М!М-задача в свободном режиме имеет временную сложность 0(п6(п)). Пример 4.8. Рассмотрим последовательность операций о= =-4 3 Е 2 Е 1 Е, где !' означает ВСТАВИТЬ(!), а Š— ИЗВЛЕЧЬ М!Н, Тогда о,=4 3, а,=2, а,=1 и и, — пустая последовательность. Начальная структура данных представляет собой последовательность множеств 1=(3, 4), 2=(2), 3=(!), 4=0. При первом выполнении 1ог-цикла выясняется, что НАЙТИ(1)= =3.
Следовательно, ответом на третью операцию в о ИЗВЛЕЧЬ М!Х будет 1. Последовательность множеств превращается в 1=(3, 4), 2=(2), 4=(1). В этот момент СЛЕД[21=4 и ПРЕД141=2, поскольку множества с именами 3 и 4 были слиты в одно множество с именем 4, При следующем прохождении с 1=-2 выясняется, что НАЙТИ(2)= =2. Таким образом, ответом на вторую операцию ИЗВЛЕЧЬ М1Х будет 2. Множество с именем 2 сливается со следующим множеством (с именем 4) и получается последовательность множеств 1 = (3, 4), 4 = (1, 2).
Два последних прохождения устанавливают, что ответ на первую операцию ИЗВЛЕЧЬ М!Н есть 3 и что 4 никогда не извлекается. Рассмотрим другое приложение — задачу определения глубины. В частности, она возникает при "приравнивании" идентификаторов в программе на языке ассемблера. Во многих языках ассемблера есть операторы, описывающие, что два идентификатора представляют одну и ту же ячейку памяти. Как только ассемблер встречает оператор, приравнивающий два идентификатора с4 и [1, он должен найти два множества Е„и Ев идентификаторов, зкви- гл. с стгэктуеы данных для зАдАч с множествхмн валентных соответственно а и р, и заменить эти два множества их объединением.
Очевидно, задачу можно смоделировать последовательностью операций ОБЪЕДИНИТЬ и НАЙТИ. Однако если внимательнее проанализировать эту задачу, можно по-другому применить структуры данных из предыдущего раздела, Каждому идентификатору соответствует графа таблицы символов, и, если несколько идентификаторов эквивалентны, удобно хранить данные о них только в одной графе таблицы символов. Это означает, что для каждого множества эквивалентных идентификаторов есть начало отсчета, т. е. место в таблице символов, где хранится информация об этом множестве, и каждый элемент этого множества имеет смещение от начала.
Чтобы найти положение идентификатора в таблице символов, надо прибавить его смещение к началу отсчета множества, которому принадлежит данный идентификатор. Но когда два множества идентификаторов становятся эквивалентными, надо изменить смещение. Эта задача корректировки смещений в абстрактном виде решается в приложении 2. Приложение 2. Задача определения глубины Дана последовательность операций двух типов: СВЯЗАТЬ(о, г) и НАЙТИ ГЛУБИНУ(о). Начнем с и неориентированных корневых деревьев, каждое из которых состоит нз единственного узла 1, 1<1<я. Операция СВЯЗАТЬ(о, г), где г — корень дерева, а о— узел другого дерева, делает корень г сыном узла о. Условия о том, что о и г принадлежат различным деревьям и что г — корень, гарантируют, что получаемый в результате граф также будет лесом.
Операция НАЙТИ ГЛУБИНУ(о) состоит в том, чтобы найти и напечатать глубину узла э в текущий момент. Если при работе с лесом использовать обычное представление в виде списков смежностей и вычислять глубину узлов очевидным образом, то сложность алгоритма будет 0(п'). Вместо этого мы представим исходный лес другим лесом, который будем называть 0-лесом. Он нужен нам только для того, чтобы можно было быстро вычислять глубины. Каждому узлу в Р-лесу приписывается целочисленный вес так, чтобы сумма весов вдоль пути в 0-лесу от узла о к корню равнялась глубине узла и в исходном лесу. Для каждого дерева в 0-лесу хранится счетчик числа узлов в этом дереве.
Вначале О-лес состоит из и деревьев, каждое из которых содержит единственный узел, соответствующий целому числу 1<1<а Начальный вес каждого узла равен нулю. Для выполнения операции НАЙТИ ГЛУБИНУ(о) мы проходим путь из узла э в корень г. Пусть пм пм..., пь — узлы на этом пути (о,=о, пь=г). Тогда ГЛУБИНА(э) = ~~.", ВЕС 1иг1. 1 1 са пРилОжения и ОБОвщения АлгОРитмА ОБъединить нАити Кроме того, применяем сжатие путей.
Каждый узел ои 1(1(й — 2, делается сыном корня г. Чтобы сохранялось сформулированное А — ! выше свойство весов, новый ВЕС узла о, должен равняться ~ ВЕС(о ] /=$ для 1(1(й. Так как новые веса можно вычислить за время 0(я), то операция НАЙТИ ГЛУБИНУ имеет ту же временную сложность, что и операция НАЙТИ. Чтобы выполнить операцию СВЯЗАТЬ(о, г), соединим деревья, содержащие узлы о и г, снова вливая меньшее дерево в большее.
Пусть Т„и ҄— деревья в В-лесу, содержащие о и г соответственно, а о' и г' — их корни. Деревья в 0-лесу не обязательно изоморфны деревьям в исходном лесу, так что, в частности, г может не быть корнем для Т„. Пусть СЧЕТ(Т) обозначает число узлов в дереве Т. Рассмотрим отдельно два случая. Случай 1. СЧЕТ(Т„)(СЧЕТ(Т,). Делаем г' сыном узла о'. Мы должны также скорректировать вес старого корня г' дерева Т„так, чтобы глубина каждого узла ш в Т„правильно вычислялась при прохождении пути из ш в о' в объединенном дереве. Чтобы сделать это, выполняем операцию НАЙТИ ГЛУБИНУ(о), а затем ВЕС [г'] — ВЕС [г'1 — ВЕС [о']+ ГЛУБИНА(о) + 1. Таким образом, глубина каждого узла в Т„эффективно увеличена на глубину узла о плюс 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
