|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[118] учётная стоимость, причем эти стоимости могут быть как больше, так и меньше реальных. Если учетная стоимость превосходит реальную, разность рассматривается как резерв (credit), который считается связанным с каким-то объектом структуры данных и рассматривается как предоплата за будущую обработку этого объекта. За счет этого резерва компенсируется разница между учетной и реальной стоимостью для тех операций, у которых учетная стоимость ниже реальной. Мы должны выбирать учётные стоимости так, чтобы фактическая стоимость не превосходила суммы учетных стоимостей, то есть чтобы резерв оставался неотрицательным в любой момент работы. Операции со стеком Проиллюстрируем метод предоплаты на уже известном примере со стеком. Напомним, что реальные стоимости операций со стеком мы считаем такими: Multipop min(s, где к - количество элементов, удаляемых из стека, s - размер стека. Присвоим этим операциям такие учётные стоимости: Multipop 0. В нашем примере учётные стоимости всех операций постоянны; возможны случаи, когда эти стоимости непостоянны и даже имеют различные асимптотики для разных операций. Покажем теперь, что выбранные нами учетные стоимости позволяют полностью покрыть реальную стоимость операций со стеком. Будем считать, что единицей стоимости операций является доллар. Воспользуемся аналогией между стеком и стопкой тарелок (см. разд. 11.1). Первоначально ни одной тарелки в стопке нет (мы начинаем с пустого стека). Когда мы добавляем тарелку к стопке, мы должны заплатить 1 доллар за операцию Push (это ее реальная цена). Один доллар остается у нас в резерве, ведь учётная цена операции Push равна двум долларам. Будем всякий раз класть этот резервный доллар на соответствующую тарелку. Тогда в каждый момент на каждой тарелке в нашей стопке будет лежать по долларовой бумажке. Доллар, лежащий на тарелке, - это предоплата за удаление тарелки из стопки. Когда мы производим операцию Pop, мы за нее ничего дополнительно не платим (учётная стоимость Pop равна Push Pop 1 1 Push Pop 2 0 нулю), а расплачиваемся за удаление тарелки лежащим на ней резервным долларом. Точно так же мы имеем возможность объявить операцию Multipop бесплатной: если надо удалить к тарелок, за удаление каждой из них мы расплатимся лежащим на ней долларом. Стало быть, избыточная плата, которую мы берем за операцию Push, покрывает расходы на операции Pop и Multipop. (стоимость любой последовательности из п операций Push, Pop и Multipop не превосходит суммарной учётной стоимости). Двоичный счётчик Решим таким же способом задачу о двоичном счётчике. Нам надо провести амортизационный анализ последовательности из п операций Increment (в исходном состоянии в счетчике записан нуль). Мы уже отмечали, что время работы этой операции пропорционально суммарному количеству установок и очисток битов. Будем считать, что каждая установка или очистка стоит 1 доллар. Установим такие учётные стоимости: 2 доллара за установку бита, 0 за очистку. При каждой установке бита одним из двух долларов учетной цены будем расплачиваться за реальные затраты на эту установку, а доллар, остающийся в резерве, будем прикреплять к установленному биту. Поскольку первоначально все биты были нулевыми, в каждый момент к каждому ненулевому биту будет прикреплен резервный доллар. Стало быть, за очистку любого бита ничего платить нам не придется: мы расплатимся за нее долларовой бумажкой, прикреплённой к этому биту в момент его установки. Теперь легко определить учётную стоимость операции Increment: поскольку каждая такая операция требует не более одной установки бита, ее учётную стоимость можно считать равной 2 долларам. Следовательно, фактическая стоимость п последовательных операций Increment, начинающихся с нуля, есть О(п), поскольку она не превосходит суммы учётных стоимостей. Упражнения 18.2-1 Предположим, что мы работаем со стеком, максимальный размер которого равен к, причем после каждых к операций делается резервная копия стека. Покажите, что суммарная стоимость п операций со стеком (включая резервное копирование) есть О(п), выбрав подходящие учётные стоимости. 18.2-2 Сделайте упражнение 18.1-3 с помощью метода предоплаты. 18.2-3 Добавим к системе операций с двоичным счётчиком операцию Reset (очистить все биты). Реализуйте счетчик на базе вектора битов таким образом, чтобы стоимость последовательности п операций Increment и Reset, примененных к счётчику, в котором первоначально находился нуль, была равна О(п), причём константа не должна зависесть от к - числа битов в счётчике. (Указание: храните номер старшего ненулевого бита). 18.3. Метод потенциалов Метод потенциалов (potential method) является обобщением метода предоплаты: здесь резерв не распределяется между отдельными элементами структуры данных (например, отдельными битами двоичного счетчика), а является функцией состояния структуры данных в целом. Эта функция называется «потенциальной энергией», или «потенциалом». Общая схема метода потенциалов такова. Пусть над структурой данных предстоит произвести п операций, и пусть Di - состояние структуры данных после г-й операции (в частности, Do - исходное состояние). Потенциал (potential) представляет собой функцию Ф из множества возможных состояний структуры данных во множество действительных чисел; эта функция называется ещё потенциальной функцией (potential function). Пусть сг- - реальная стоимость г-й операции. Учетной стоимостью (amortized cost) г-й операции объявим число с,- = с,- + Ф(Д-)-Ф(Д- 1),(18.1) т.е. сумму реальной стоимости операции плюс приращение потенциала в результате выполнения этой операции. Тогда суммарная учетная стоимость всех операций равна пп J> = с,- + Ф(£)п)-Ф(До).(18.2) 8 = 18 = 1 Если нам удалось придумать функцию Ф, для которой Ф( Ога) Ф(-Оо), то суммарная учетная стоимость даст верхнюю оценку для реальной стоимости последовательности п операций. Не ограничивая общности, можно считать, что Ф(-Оо) = 0 (см. упр. 18.3-1). Говоря неформально, если разность потенциалов Ф(-Ог) - Ф( Ог-1) положительна, то учетная стоимость г-й операции включает в себя резерв («предоплату» за будущие операции); если же эта разность отрицательна, то учетная стоимость г-й операции меньше реальной, и разница покрывается за счет накопленного к этому моменту потенциала. |
Среды: 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 | ||