|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[147] нами) утверждением о том, что стоимость т операций с непересекающимися множествами, включающих га операций Make-Set, есть @(та(т, га)). В самом деле, эта оценка говорит, что стоимость в расчёте на одну операцию есть а(т, га). Если га фиксировано, а т растёт, то из-за сжатия путей деревья с каждым шагом всё более «упрощаются» (всё больше становится вершин, напрямую связанных с корнем), так что стоимость операции падает. Во всех практических приложениях можно считать, что а(т, га) 4. В самом деле, поскольку функция Аккермана является возрастающей по каждому переменному и т га, имеем А(4, [т/п\) > А(4,1) = А(3, 2) = 22** 17, что много больше числа атомов в наблюдаемой части Вселенной (к, 1080). Поэтому для всех встречающихся на практике значений га имеем А(4, то/га ) lg га и а(т,п) 4. Мы не доказываем оценки, связанной с функцией Аккермана, а ограничиваемся более слабой оценкой 0(mlg*ra). Вспомним определение функции lg* (с. ??). По определению, lg* 1 = 0 и lg* га = min { г : lg lg ... lg га 1 ) 4-„- г раз для га > 1. Неравенство в определении функции lg* можно перепи-] сать так: га 22 > j (j - число двоек в формуле). Оценка 0(mlg* га), которую мы докажем ниже, слабее, чем сформулированная без доказательства оценка 0(та(т, га)), но с практической точки зрения разница невелика. В самом деле, lg* 22 = lg* 265536 = 5, так что во всех практических вопросах можно считать, что lg* га 5 - вряд ли нам встретится множество, в котором более 265536 элементов. Свойства рангов Чтобы доказать оценку 0(mlg*ra) для времени работы с системой непересекающихся множеств, нам понадобятся некоторые свойства рангов. Напомним, что мы работаем с системой непересекающихся множеств, реализованной с помощью леса, с объединением по рангам и сжатием путей (см. разд. 22.3); через т обозначено суммарное число операций Make-Set, Find-Set и Union, а через га - число операций Make-Set. Лемма 22.2 Для всякой вершины ж, кроме корня, rank[x] < гага/г[р[ж]] (напомним, что для корня р[х] = ж). При создании множества {ж} имеем rank[x] = 0, далее rank[x] может только возрастать и перестаёт меняться, когда ж перестаёт быть корнем в своём дереве. Доказательство. Всё это непосредственно следует из описания процедур Make-Set, Union и Find-Set в разделе 22.3. Подробности мы оставляем читателю (упр. 22.4-1). Пусть ж - вершина одного из наших деревьев. Число вершин в поддереве с корнем х (включая саму ж) назовем ее размером (size) и обозначим size(a:). Лемма 22.3 Если х - корень одного из деревьев, то size (ж) 2rankx\ Доказательство. Достаточно проверить, что каждая из операций Make-Set, Find-Set и Link сохраняет истинность утверждения «size(x) 2jrank[x] дЛЯ всех КОрНей ж». Операция Find-Set не меняет ни размеров корней, ни рангов каких бы то ни было вершин. Операция Маке-8ет(ж) также не нарушает утверждения леммы: не меняя рангов и размеров уже существующих деревьев, она создаёт новое дерево с единственной вершиной, для которой неравенство очевидным образом выполнено. Рассмотрим операцию Link(x,j/) (не ограничивая общности, можно считать, что rank[x] rank[y]). В результате этой операции ранг или размер может измениться только у вершины у. Если rank[x] < rank[y], то размер у увеличивается, а ранг не меняется, так что неравенство size(y) 2гапку\ остаётся верным. Если же гапк[х] = гапк[у], то, обозначая через size[y] и гапк[у] размер и ранг у после операции Link, имеем size[y] = size[x] + size[y] и rank[y] = rank[y] + 1. Отсюда size[y] = size[x] + size[y] 2rank + 2rank = 2rank+1 = 2rank. Лемма 22.4 Число вершин ранга г не превосходит га/2г (для любого целого г 0). Доказательство. Зафиксируем число г. Всякий раз, когда какой-либо вершине у присваивается ранг г (в строке 2 процедуры Make-Set или в строке 5 процедуры Link), будем привешивать метку ко всем вершинам поддерева с вершиной у. Поскольку вершина у в этот момент является корнем одного из деревьев, лемма 22.3 показывает, что число помечаемых вершин не меньше 2Г. Наши процедуры устроены так, что каждая вершина будет помечена не более одного раза. Стало быть, га (число меток) 2Г • (число вершин ранга г), откуда всё и следует. Следствие 22.5 Ранг любой вершины не превосходит [lg raj. Доказательство. См. лемму 22.3 или 22.4 Доказательство оценки для времени работы При доказательстве оценки нам будет удобнее работать с операцией Link, а не Union. Пусть дана последовательность Si, состоящая из mi операций Make-Set, Find-Set и Union. Заменим каждую операцию Union на две операции Find-Set и одну операцию Link; получится последовательность 5*2 из т2 операций Make-Set, Find-Set и Link. Лемма 22.6 Если стоимость выполнения последовательности 5*2 в худшем случае есть 0(ra2lg* п), то стоимость выполнения последовательности 5*1 в худшем случае есть О (mi lg* п), где п - число операций Make-Set. Доказательство. Немедленно следует из очевидного неравенства mi т2 3rai. Теорема 22.7 Предположим, что над системой непересекающихся множеств (первоначально пустой) произвели т операций Make-Set, Find-Set и Link, из которых п операций были операциями Make-Set. Тогда при использовании реализации с помощью леса со сжатием путей и объединением по рангам общая стоимость этой последовательности операций есть 0(m\g* п). Доказательство. Стоимость каждой из операций Make-Set и Link есть, очевидно, 0(1), а их суммарная стоимость есть тем самым О (га). Займемся операциями Find-Set. Очевидно, стоимость операции Find-Set) пропорциональна длине пути поиска от ж к корню (до сжатия). Стало быть, нам надо оценить суммарную длину путей поиска, возникавших в процессе выполнения всех операций Find-Set и доказать, что она есть 0(ralg* п). В процессе выполнения каждой из операций Find-Set мы двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Заметим, что на каждом шаге ранг вершины строго возрастает: если и - вершина, встретившаяся на пути поиска, a v - следующая вершина, то есть v = р[и], то rank[v] > гапк[и]. Вершина и может неоднократно встречаться в путях поиска при выполнении рассматриваемой в теореме последовательности операций. При этом за ней могут (и скорее всего будут) идти разные вершины: если в некоторый момент за и следовала вершина v, которая не была корневой, то после сжатия путей за и будет следовать уже не v, а корень дерева (на момент первого поиска), то есть вершина большего ранга, чем v. (Это простое наблюдение играет к дальнейшем ключевую роль.) Наблюдая за ростом ранга при переходе от вершины к её родителю, мы отдельно оценить количество шагов, при которых ранг сильно растёт, и количество шагов, когда он растёт не сильно. Вы- |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||