1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 37
Текст из файла (страница 37)
В[1) остается безопасным до тех пор, пока он не будет разбит. Когда В[В разбивается, индекс одного подблока, назовем его В[4), помещается в ОЖИДАНИЕ. Другой подблок по-прежнему называется ВИ. Очевидно, что объединение этих двух подблоков, т. е. В[1[0В[д[, безопасно для рассматриваемого разбиения, поскольку оно совпадает со старым блоком ВИ.
Дальнейшее разбиение образует такие блоки В[4>),..., В[>! ), что дь..., ол входят в ОЖИДАЙИЕ, а объединение Я=ВЫ 0 В[у>[ 0 . 0 В[у,) безопасно. Когда д> при некотором 1(1(1(й) удаляется из множества ОЖИДАНИЕ, строки 6 — 14 снова делают В[4>[ н )к — В[у>[ безопасными. Изложим теперь зто формально. Докажем справедливость утверждения (4.6) для всех 1 индукцией по числу выполнений строк 4 — 14. Когда алгоритм заканчивает работу, множество ОЖИДАНИЕ пусто, и, значит, из (4.6) будет вытекать, что каждый блок окончательного разбиения и' безопасен для и'.
Для доказательства базиса возьмем 0 выполнений, тогда (4.6) тривиально, поскольку 1~ОЖИДАНИЕ для всех 1 1((>=р. Для проведения шага индукции предположим, что после выполнения строки 14 1>1 ОЖИДАНИЕ. Если число 1 всегда ранее входило в ОЖИДАНИЕ, то оно имеет значение >, которое определялось в строке 4. Легко показать, что цикл в строках 6 — 14 делает В[!1 безопасным для разбиения, получающегося после выполнения строки 14 Это мы уже обосновали после определения понятия "безопасный". Если число 1 не входило в ОЖИДАНИЕ во время предыдущего ш> С!3.
РАЗБИЕНИЕ выполнения цикла до строки 14, то по предположению индукции найдется такой список оь ..., ол, что (4.6) было справедливо для 1 на предыдущем этапе. Кроме того, в строке 4 обязательно 1~1, Случай 1. 1 нет в Ь=(оь оь ..., о ). В строках 9, 10 могло произойти разбиение нескольких блоков. Для каждого такого блока В[о„[, 1(г(й (т. е. [=д„), добавим в 1. индекс блока, образованного в строке 8. Благодаря строке 11 список Ь по-прежнему будет состоять только из индексов, входящих в ОЖИДАНИЕ. Если сам блок ВИ не разбит, то В[1[ и множество блоков с индексами из 1 все еще образуют множество, безопасное для текущего разбиения, так что (4.6) удовлетворяется.
Если же блок В[1[ разбит, надо также добавить в Ь индекс о, выбранный в строке 8, когда 1=1. Следовательно, множество В[В ([ ([ В[г! будет безопасно для текущего разбиения. гес Случай 2. 1 находится в Ь=(оь оь ..., оь). Без потери общности будем считать, что (=до Рассуждение проводится почти так же, как в случае 1, но д, в конце рассматриваемой итерации строк 4 — 14 может не входить в ОЖИДАНИЕ.
Мы знаем, что каждый блок В текущего разбиения будет либо подмножеством множества 1 '(В[а,[), либо не будет с ним пересекаться. Пусть Т= =-ВИ ([ ([ В[г), где список Ь модифицирован, как в случае 1, Если ~еl Вт[ '(В[у,[), то, разумеется, В([[-'(Т)=[б. Если Вдг '(В[у,))= =(й, то аналогично случаю 1 можно доказать, что В Пг' '(Т)=(Р[ или В~~ '(Т). Наконец, когда алгоритм 4.5 заканчивает работу, множество ОЖИДАНИЕ должно быть пусто. Следовательно, из (4.6) вытекает, что для каждого 1 блок ВИ безопасен для окончательного разбиения. С) Теорема 4.8. Алгоритм 4.5 правильно вычисляет грубейшее разбиение множества Я, совместшвое с и и 1'.
Д о к а з а те л ь с т в о. Лемма 4.7 показывает, что выход и' алгоритма 4.5 совместим с и и 1. Надо доказать, что разбиение и' грубо, насколько возможно. Простая индукция по числу блоков, разбиваемых в строках 9, 10, показывает, что каждое такое разбиение, сделанное алгоритмом, необходимо для совместимости. Оставляем эту индукцию в качестве упражнения. Теперь мы должны детально исследовать реализацию алгоритма 4.5, чтобы показать, что время его работы составляет 0(п1ойп), где п=[Щ.
Основным при оценке времени работы будет демонстрация того, что цикл в строках 6 — 14 можно выполнить за время, пропорциональное [[ОБРАЩЕНИЕ[[. Наша первая задача — эффективно найти подходящее множество чисел 1 в строке 6. Нам понадобится такой массив БЛОК, что БЛОКИ вЂ” индекс блока, содержащего 1. Начальное состояние массива БЛОК можно по- ю гл. 4. стегктгеы длнных для злдлч с миожаствлми строить за 0 (и) шагов, после строки 9 скорректировать его за время, не большее того, что тратится на формирование списка В(о! в этой строке.
Следовательно, поскольку нас интересует только порядок временной сложности, можно не учитывать время, затрачиваемое иа работу с массивом БЛОК. С помощью массива БЛОК легко построить список ЗСПИСОК чисел 1, необходимых в строке 6, за 0(!!ОБРАЩЕНИЕ!!) шагов. Для каждого элемента а, входящего в ОБРАЩЕНИЕ, индекс блока, содержащего а, добавляем в )СПИСОК, если его там еще нет. Для каждого 1 хранится счетчик числа элементов, входящих в ОБРАЩЕНИЕ, которые входят также и в ВЦ!. Если этот счетчик достигнет величины !!ВЦ)!!, то ВЦ! ~ ОБРАЩЕНИЕ и 1 удаляется из списка 3СПИСОК.
Используя БЛОК, можно для каждого), входящего в 3СПИСОК, построить также список ПЕРЕСЕЧЕНИЕЦ), в который войдут все целые числа, принадлежащие обоим множествам ВЦ! и ОБРАЩЕНИЕ.Чтобы быстро удалитьэлементы списка ПЕРЕСЕЧЕНИЕ(1) из ВЦ! и добавить их в В1о), надо поддерживать списки В!1), 1<1(д, в дважды связанном виде, т. е. с указателями как к следующей, так и к предыдущей компонентам.
Строки 9 и 10 требуют О(!)В[о!!!) шагов. Для данного выполнения !ог-цикла суммарное время, затрачиваемое на нахождение подходящих чисел 1 и иа выполнение строк 7 — 10, составляет 0(!!ОБРАЩЕНИЕ!!). Кроме того, легко видеть, что тест в строках 12 — 14, если его выполнять должным образом, занимает 0(!!В(д)!!) времени, так что общее время есть 0(!!ОБРАЩЕНИЕ!!). Осталось рассмотреть строку 11. Чтобы быстро сказать, входит ли / в ОЖИДАНИЕ, образуем другой массив В ОЖИДАНИИЦ1. Начальное состояние В ОЖИДАНИИ можно построить за 0(н) шагов и без труда корректировать его в строках 1! — 14. Таким образом, мы доказали следующую лемму.
Лемма 4.8. !ог-цикл в строках 6 — 14 на рис. 4.35 можно реализовать за 0(!!ОБРАЩЕНИЕ!!) шагов. Доказательство. В силу изложенного выше. ) Теорема 4.9. Алгоршпм 4.5 можно ре лизовата за время 0 (и 1ойн). Д о к а з а т е л ь с т в о, Рассмотрим условия, при которых блок, содержащий целое число з и не представленный в множестве ОЖИДАНЙЕ, может попасть туда. В строке 1 это может случиться лишь один раз. В строке 11 это произойти не может; даже если зЕВ!9), поскольку тогда з было бы в ВЦ! еще раньше, а индекс 1 уже входил в ОЖИДАНИЕ. Если это случилось в строках 13 и !4, то число г находится в блоке, размер которого не больше половины размера того блока, куда оио входило в тот предыдущий момент, когда индекс множества, содержащего з, попал в ОЖИДА- 136 1.13. РАЗБИЕНИЕ НИЕ.
Отсюда можно заключить, что индекс множества, содержащего з, попадает в ОЖИДАНИЕ ие больше 1+!ойп раз, Следовательно, з не может быть в блоке 1', который выбирался в строке 4 более чем 1+!оп п раз. Допустим, что на каждый элемент з из В(11 каждый раз налагается штраф, пропорциональный !!1 '(з)!!, так что сумма всех штрафов равна сложности выполнения цикла в строках 6 — 14. Тогда существует такая постоянная с, что за одно выполнение цикла элемент Б штрафуется не более чем на с!!1 '(з)!!. Как мы уже показали, элемент з не может попасть в выбираемый список ВИ более чем 0(!паап) раз, так что суммарный штраф, налагаемый на него, составляет 0 (!!1-' (з)!! !оп и).
Так как сумма ~!!1-' (з)!! должна равняться 5А и, то общая сложность всех выполнений 1ог-цикла есть 0(п(одп). Легко видеть, что сложность остальной части алгоритма 4.5 есть 0(п); теорема доказана, П Алгоритм 4.5 имеет несколько приложений. Одно из важных приложений — минимизация числа состояний конечного автомата. Дан конечный автомат М= (5, 1, 6, Б„Р) и требуется найти эквивалентный ему автомат М' с наименьшим числом состояний. Для каждого состояния з и входного символа а обозначим через 6(з, а) очередное состояние автомата. Вначале все состояния автомата М можно разбить на множество Р допускающих состояний и множество 5 — Р недопускающих состояний. Задача минимизации числа состояний автомата М эквивалентна нахождению грубейшего разбиения и' множества 5, совместимого с начальным разбиением (Р, 5 — Р) и такого, что если состояния з и 1 находятся в одном блоке разбиения и', то состояния 6(з, а) и 6 (1, а) также находятся в одном блоке автомата М' для каждого входного символа а.
Единственное отличие этой задачи от задачи, решаемой алгоритмом 4.6, состоит в том, что 6 — отображение из 5 х 1 в 5, а не из 5 в 5. Однако можно трактовать 6 как множество (6,„6,„ ..., 6, ) функций на 5, где 6, — сужение функции 6 йа а. Алгоритм 4.6 легко модифицировать так, что он справится с этой более общей задачей, помещая в множество ОЖИДАНИЕ пары (1, 6,). Каждая пара (1, 6,) состоит из индекса 1 некоторого блока разбиения и функции 6., по которой проводится разбиение.
Вначале ОЖИДАНИЕ=((1, 6,)!1=1 или 2 и аЕ1), поскольку начальное разбиение (Р, 5 — Р) состоит из двух блоков. Всякий раз, когда блок В(1) разбивается на В(11 и В(111, каждая допустимая функция 6, спаривается с ! и 11. Остальные детали оставляем в качестве упражнения. 1ВХ гл. к стввктгвы данных для задач с множествами 4.14. РЕЗЮМЕ На рис. 4.36 приведены различные структуры данных, рассмотренные в этой главе, типы операций, которые можно совершать на их основе, и принимаемые нами соглашения о размере и природе того универсального множества, откуда брались элементы.
Структура данных Тип универсума Допустимые операции в худшем случае среднее 0(и*) 0(и !од п) Древовидная структура из алгоритма 4.3 не более 0(а 6 (а)) не более 0(а 0 (п)) Рвс. 4.3б. Сводка свойств структур даввык. Дерево двоичного поиска Любое упорядоченное множество Множество целых чисел от ! до а ПРИНАДЛЕЖАТЬ ВСТАВИТЬ УДАЛИТЬ М!Н ПРИНАДЛЕЖАТЬ ВСТАВИТЬ УДАЛИТЬ ОБЪЕДИНИТЬ НАЙТИ Время выполнения п операций над множе- ствами размера и УП РАЖ Н Ь НИЯ УПРАЖНЕНИЯ 4.1. Приведите подмножество семи основных операций из разд.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
