|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[142] имости операции Fib-Heap-Decrease-Key (которая есть 0(1)) и операции Fib-Heap-Extract-Min (которая есть 0(D(n))). Упражнения 21.3-1 Каким образом может появиться помеченная вершина в корневом списке? 21.3-2 Докажите оценку 0(1) для учётной стоимости операции Fib-Heap-Decrease-Key, используя метод группировки (раздел 18.1). 21.4. Оценка максимальной степени Для получения обещанных оценок О (lgra) для учётной стоимости операций Fib-Heap-Extract-Min и Fib-Heap-Delete осталось показать, что максимальная степень D(n), которую может иметь какая-либо вершина в фибоначчиевой куче с га вершинами, не превосходит О (lgra). Как показывает упражнение 21.2-3, если все деревья в фибоначчиевой куче являются неупорядоченными биномиальными деревьями, то D(n) = [lgraJ- Но операции вырезания, которые происходят во время исполнения процедуры Fib-Heap-Decrease-Key, приводят к тому, что деревья в фибоначчиевой куче более не являются биномиальными. Мы покажем, что тем не менее при выполнении описанных операций остаётся в силе оценка D(n) = 0(lg2ra). Точнее, мы установим, что D(n) 1°8у п\ > гДе V = (1 + л/5)/2. Для каждой вершины фибоначчиевой кучи через size (ж) обозначим число вершин в поддереве с корнем ж, считая саму вершину ж. (Вершина ж не обязана быть корневой вершиной кучи.) Мы покажем, что величина size(a:) экспоненциально зависит от degree[x]. (Напомним, что поле degree[x] поддерживается равным степени вершины ж.) Лемма 21.1. Пусть ж - произвольная вершина фибоначчиевой кучи, и пусть degree[x] = к. Тогда степени к детей вершины ж не меньше О, 0,1, 2, 3,..., к - 2, если их расположить в надлежащем порядке. Доказательство. Для вершин, не входящих в корневой список, определим «модифицированную степень», которая на единицу больше реальной степени для помеченных (и совпадает с ней для непомеченных). Смысл этого такой: поскольку при удалении ребёнка у вершины делается пометка, то её модифицированная степень не меняется, а добавление детей возможно только для вершин в корневом списке. Таким образом, модифицированная степень есть степень на момент (последнего) выбытия вершины из корневого списка. Поскольку модифицированная степень отличается от реальной не более чем на 1, достаточно доказать, что у вершины (реальной) степени к дети имеют модифицированную степень не менее 0,1, 2,..., к - 1. Ясно, что это свойство сохраняется при удалении одного из детей. Кроме того, оно сохраняется при добавлении к вершине степени к другой вершины степени к (при подчинении одной вершины корневого списка другой первая делается непомеченной, так что её реальная степень равна модифицированной). □ Теперь оценим число потомков для вершины степени к, используя числа Фибоначчи. Напомним, что к-е число Фибоначчи Fk определяется так: Оесли к = О, Fk = < 1если к = 1, Ffc i + Ffc 2 если к 2. Лемма 21.2. для любого к > 0. к Fk+2 = 1 + V F 8 = 0 Доказательство. При к = 0 это верно: 1 + Y=o Fi = 1 + Fq = 1 + 0 = 1 = F2. Рассуждая по индукции, предполагаем, что Fk+\ = 1 + YZo F-Тогда k-i Fk+2 = Fk + Fk+1 = Fk+ l 1 + JFi =1 + X>8. 8 = 0 /8 = 0 □ Теперь мы уже можем оценить число вершин в поддереве, если известна степень его корня. Напомним, что Fk+2 к\ где f = (1 + у/5)/2 = 1.61803... - «золотое сечение» (2.14). (Это неравенство доказано в упр. 2.2-8.) Лемма 21.3. Пусть х - вершина фибоначчиевой кучи, имеющая степень к или больше. Тогда size(a;) Fk+2 ipk, где ip = (1 + а/5)/2. Доказательство. По лемме 21.1 вершина х имеет среди своих детей вершины степени не менее 0, 0,1, 2, 3,..., к - 2. Рассуждая по индукции, мы можем считать, что для детей доказываемое утверждение верно. (При к = 0 число Fk+2 равно 1 и оценка очевидна.) Задачи к главе 21 437 Складывая число вершин в поддеревьях и прибавляя саму вершину ж, получаем, что she(x) > (F2 + F2 + F3 + F4 + ... + Fk) + 1 = = (F0 + Fi + F2 + ... + Fk) + 1 = Fk+2 (мы используем равенство Fo + F\ = F2 и лемму 21.2).□ Следствие 21.4. Максимальная степень D(n) какой-либо вершины в фибоначчиевой куче с га вершинами есть О (lgra). Доказательство. Пусть х - произвольная вершина такой кучи и пусть k = degree[x]. По лемме 21.3 имеем га size(a:) ipk, остаётся взять логарифм по основанию (р. □ Упражнения 21.4-1 Профессор утверждает, что высота фибоначчиевой кучи из га элементов не превышает О (lgra). Покажите, что он ошибается и что существует последовательность операций рассмотренных нами типов, которая приводит к куче, состоящей ровно из одного дерева, являющегося линейной цепью из га вершин. 21.4-2 Изменим правила и будем считать, что вершина перемещается в корневой список, когда она потеряла к своих потомков, где к - некоторая константа (до сих пор мы считали, что к = 2). При каких значениях к можно утверждать, что D(n) = O(lgra)? Задачи 21-1 Другой способ удаления элемента Профессор предложил следующий вариант процедуры Fib-Heap-Delete, утверждая, что новая процедура работает быстрее в том случае, когда удаляемая вершина - не минимальная. New-Delete(#, х) 1if х = тгп[Н] 2then Fib-Heap-Extract-Min (Я) 3else у <- р[х] 4if у ф nil 5then Сит(Я, ж, у) 6Cascading-Cut, у) 7добавить детей вершины ж в корневой список кучи Я 8удалить ж из корневого списка кучи Я |
Среды: 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 | ||