Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 109
Текст из файла (страница 109)
(См. упр. 17.3.1, в котором идет речь о том, как быть в ситуации, когда Ф(Ро) ф О.) Интуитивно понятно, что если разность потенциалов Ф(Р,) — Ф(Р; 1) для з-й операции положительна, то амортизированная стоимость с; представляет переоценку з-й операции и потенциал структуры данных возрастает. Если разность потенциалов отрицательна, то амортизированная стоимость представляет недооценку 1-й операции и фактическая стоимость операции выплачивается за счет уменьшения потенциала. Амортизированные стоимости, определенные уравнениями (17.2) и (17.3), зависят от выбора функции потенциала Ф.
Амортизированные стоимости, соответствующие разным функциям потенциала, могут различаться, при этом все равно оставаясь верхними границами фактических стоимостей. При выборе функций потенциалов часто допустимы компромиссы; то, какую функцию лучше всего использовать, зависит от оценки времени, которую нужно получить. Глава ! 7. Амортизационный анализ 497 потенциал; следовательно, Ф(Р,) > О = Ф(Ро) .
Таким образом, полная амортизированная стоимость п операций, связанная с функцией Ф, представляет собой верхнюю границу фактической стоимости. Теперь вычислим амортизированные стоимости различных стековых операций. Если г-я операция над стеком, содержащим а объектов, — операция РОзн, то разность потенциалов равна Ф(Р,) — Ф(Р; 1) = (а + 1) — а =1. Согласно уравнению (17.2) амортизированная стоимость операции РОзн равна с, = с; + Ф(Р;) — Ф(Р; 1) =1+1 Предположим, что зья операция над стеком — операция Мш.т1рор(5, 1с), и что из него извлекается lс' = ш(п(19, э) объектов.
Фактическая стоимость этой операции равна Йз, а разность потенциалов— Ф(Р;) — Ф(Р; 1) = — lс'. Таким образом, амортизированная стоимость операции М17ьт1рор равна сг + Ф(Рг) Ф(Рг-1) = й' — й' Аналогично можно показать, что амортизированная стоимость операции Рог также равна О. Амортизированная стоимость каждой из трех операций равна 0(1), поэтому полная аморгизированная стоимость последовательности из п операций равна 0(п). Мы уже доказали, что Ф(Р;) > Ф(Ро), поэтому полная амортизированная стоимость п операций является верхней границей полной фактической стоимости. Поэтому в наихудшем случае стоимость и операций равна 0(п). Увеличение показаний бинарного счетчика В качестве другого примера применения метода потенциалов снова обратимся к задаче о приращении показаний бинарного счетчика.
На этот раз определим потенциал счетчика после выполнения гтй операции 1хскемехт как количество (зг содержащихся в счетчике единиц после этой операции. Часть 1К зсовершенствованные методы разработки и анализа 498 Вычислим амортнзированную стоимость операции 114сквмвмт. Предположим, что з-я операция 1нсквмемт обнуляет Ц бит. В таком случае фактическая стоимость этой операции не превышает значения 11+ 1, поскольку вдобавок к обнулению 11 бит значение 1 присваивается не более чем одному биту.
Если 6; = О, то в ходе выполнения 1-й операции обнуляются все /с бит, так что 6, 1 = 1з = /с. Если 61 ) О, то выполняется соотношение 6, = 6, 1 — 11 + 1. В любом случае справедливо неравенство 61 < 6, 1 — 1, + 1 и разность потенциалов равна Ф(Р;) — Ф(Р1 1) < (Ьв 1 — Ц+ 1) — Ь; 1 =1 11 Таким образом, амортизированная стоимость определяется соотношением с„= с, + Ф(Р1) — Ф(Р; 1) < (11 + 1) + (1 — 11) =2. Ф(Р ) + Ф(Р1) 1=1 с=1 (17.4) При всех 1 < з < п выполняется неравенство с, < 2.
В силу соотношений Ф(Ро) = 6о н Ф(Р„) = 6„полная фактическая стоимость п операций 1мсквмвмт равна с;(~~ 2 — 6„+Ьр =2п — Ь +Ьо. В частности, заметим, что, поскольку Ьо < 6, при 1с = 0(п) полная фактическая стоимость равна 0(п). Другими словами, если выполняется не менее и = П(й) операций 11чсккыв1чт, полная фактическая стоимость независимо от начальнопз показания счетчика равна 0(п).
Если вначале показания счетчика равны нулю, то Ф(Ро) = О. Поскольку при всех 1 справедливо неравенство Ф(Р;) ) О, полная амортизированная стоимость последовательности из п операций 1мсклмвмт является верхней границей полной фактической стоимости, поэтому в наихудшем случае стоимость п операций 1мсквмвмт равна 0(п). Метод потенциалов предоставляет простой способ анализа счетчика даже в том случае, когда отсчет начинается не с нуля. Пусть изначально показание счетчика содержит Ьо единиц, а после выполнения и операций 1мсккмн1чт — 6„ единиц, где О < Ьо, Ь„< )с.
(Напомним, что lс — количество битов в счетчике.) Тогда уравнение (17.3) можно переписать следующим образом: Глава 77. Амортизационный анализ 499 Упражнения 17.3.1 Предположим, задана такая функция потенциала Ф, что при всех з выполняется неравенство Ф(Рз) > Ф(Рс), но Ф(Рс) зй О. Покажите, что существует функция потенциала Ф', такая, что Ф'(Рс) = О и Ф'(Р;) > О для всех з > 1, и соответствующая функции Ф' амортизированная стоимость такая же, как и для функции Ф. 17.3.1 Еще раз выполните упр. 17.1.3, используя метод потенциалов. 17.3.3 Рассмотрим обычную и-элементную бинарную неубывающую пирамиду.
Пусть в этой структуре данных поддерживаются операции 1ызект и ЕхткАст-Мпч, для выполнения которых в наихудшем случае требуется время 0(1яп). Определите функцию потенциала Ф, такую, что амортизированная стоимость операции 1изккт равна 0(1к и), а амортизированная стоимость операции ЕхткАст-Мпч— 0(1), и покажите, что она работает. 17.3.4 Чему равна полная стоимость выполнения и стековых операций РОзн, РОЕ и М~л.ти'ор, если предположить, что в начале стек содержит ас объектов, а в конце — вн объектов? 17.3.5 Предположим, что изначально показание счетчика не равно нулю, а определяется числом, содержащим в двоичном представлении 6 единиц. Покажите, что стоимость выполнения и операций 1мскемемт равна 0(п) при условии, что и = й(Ь).
(Не следует предполагать, что Ь вЂ” константа.) 173.б Покажите, как реализовать очередь на основе двух обычных стеков (см. упр. 10.1.б) таким образом, чтобы амортизированная стоимость каждой из операций ЕМООЕОЕ и РЕООЕОЕ была равна 0(1). 17.3. 7 Разработайте структуру данных для поддержки следующих двух операций над динамическим мультимножеством целых чисел Я, в котором могут содержаться одинаювые значения: 1изект(Я,х), вставляющая х в 5.
Пекете-1,Акбек-НАее (Я), удаляющая наибольшие (~Я~ /21 элементов из Я. Поясните, как реализовать зту структуру данных, чтобы любая последовательность из гп указанных операций выполнялась за время 0(пт). Ваша реализация должна также включать способ вывода элементов Я за время 0(~5(). 500 Части ГЕ Усовершенствованные методы разработки и аназиза 17.4.
Динамические таблицы В некоторых приложениях заранее не известно, сколько элементов будет храниться в таблице. Может возникнуть ситуация, когда для таблицы выделяется место, а впоследствии оказывается, что его недостаточно. В этом случае приходится выделять больший объем памяти и копировать все объекты из исходной таблицы в новую, большего размера.
Аналогично, если из таблицы удаляется много объектов, может понадобиться преобразовать ее в таблицу меньшего размера. В этом разделе исследуется задача о динамическом расширении и сжатии таблицы. Методом амортизационного анализа будет показано, что амортизированная стоимость вставки и удаления равна всего лишь 0(1), даже если фактическая стоимость операции больше из-за того, что она приводит к расширению или сжатию таблицы. Более того,мы выясним, как обеспечить соблюдение условия, при котором неиспользованное пространство динамической таблицы не превышает фиксированную долю ее полного пространства. Предполагается, что в динамической таблице поддерживаются операции ТАВее-1мзект и ТАнее-1)ееете.
В результате выполнения операции ТАнее1мзект в таблицу добавляется элемент, занимающий одну ячейку (з!о1), — пространство для одного элемента. Аналогично операцию ТАвее-Пн.ете можно представлять как удаление элемента из таблицы, в результате чего одна ячейка освобождается. Подробности метода, с помошью которого организуется таблица, не важны; можно воспользоваться стеком (раздел 1О.1), пирамидой (глава 6) или хеш-таблицей (глава ! 1). Для реализации хранилиша объектов можно также использовать массив или набор массивов, как это было сделано в разделе 10.3.
Оказывается, достаточно удобно применить концепцию, введенную при выполнении анализа хеширования (глава 11). Определим коэффициент заполнения (1оаб Гасгог) о(Т) непустой таблицы Т как количество хранящихся в них элементов, деленное на ее размер (измеряемый в количестве ячеек). Размер пустой таблицы (в которой нет ни одного элемента) примем равным нулю, а ее коэффициент заполнения — единице.
Если коэффициент заполнения динамической таблицы ограничен снизу константой, ее неиспользованное пространство никогда не превышает фиксированной части ее полного размера. Начнем анализ с динамической таблицы, в которую выполняются только вставки. Впоследствии будет рассмотрен более общий случай, когда разрешены и вставки, и удаления. 17.4.1. Расширение таблицы Предположим, что место для хранения таблицы выделяется в виде массива ячеек. Таблица становится заполненной, когда заполняются все ее ячейки или (что 50! Глава ! 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
