Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 102
Текст из файла (страница 102)
Этот потенциал связан со структурой данных в целом, а не с ее отдельными объектами. Метод потенциалов работает следующим образом. Мы начинаем с исходной структуры данных Ро, над которой выполняется и операций. Для всех г = = 1, 2,...,п обозначим через с; фактическую стоимость Гий операции, а через Р; — структуру данных, которая получается в результате применения 1-й операции к структуре данных Р; и Потенциальная функция (рогепба1 йшсйоп) Ф отображает каждую структуру данных Р; на действительное число Ф (Р;), которое является лольенииалаи (рогепйа!), связанным со структурой данных .0;. Амортизироеанпая стоимость (ашогг1гед созг) с; г-й операции определяется соотношением с; = с;+ Ф(Рь) — Ф(Р; 1).
(17.2) Поэтому амортизированная стоимость каждой операции — это ее фактическая стоимость плюс приращение потенциала в результате выполнения операции. Согласно уравнению (17.2), полная амортизированная стоимость и операций равна ь и и с; = ~~~ (с;+Ф(Р,) — Ф(Р; 1)) = ~с;+ Ф(.0„) — Ф(.0о). (17.3) Второе равенство следует из уравнения (А.9), поскольку слагаемые Ф (Р;) — так называемые телескопические. Если потенциальную функцию Ф можно определить таким образом, чтобы выполнялось неравенство Ф (Р ) > Ф (Ро), то полная амортизированная стоимость с; является верхней границей полной фактической стоимости 2,'," с;.
На Часть ! Ч. Усовершенствованные методы разработки и анализа 492 практике не всегда известно, сколько операций может быть выполнено, поэтому, если наложить условие Ф (Р;) > Ф (Ро) для всех т', то, как и в методе бухгалтерского учета, будет обеспечена предоплата.
Часто удобно определить величину Ф (Ро) равной нулю, а затем показать, что для всех 1 выполняется неравенство Ф(Р;) > О. (См. упражнение 17.3-1, в котором идет речь о простом способе справиться со случаями, когда Ф (Ро) ф О.) Интуитивно понятно, что если разность потенциалов Ф (Р,) — Ф (Р, 1) для 1-й операции положительна, то амортизированная стоимость с; представляет переоценку 1-й операции и потенциал структуры данных возрастает. Если разность потенциалов отрицательна, то амортизированная стоимость представляет недооценку 1-й операции и фактическая стоимость операции выплачивается за счет уменьшения потенциала.
Амортизированные стоимости, определенные уравнениями (17.2) и (17.3), зависят от выбора потенциальной функции Ф. Амортизированные стоимости, соответствующие разным потенциальным функциям, могут различаться, при этом все равно оставаясь верхними границами фактических стоимостей. При выборе потенциальных функций часто допустимы компромиссы; то, какую потенциальную функцию лучше всего использовать, зависит от оценки времени, которую нужно получить. Стековые операции Чтобы проиллюстрировать метод потенциала, еще раз обратимся к примеру со стековыми операциями Ризи, РоР и Ми~лроР. Определим потенциальную функцию Ф для стека как количество объектов в этом стеке.
Для пустого стека Рд, с которого мы начинаем, выполняется соотношение Ф (Ро) = О. Поскольку количество объектов в стеке не может быть отрицательным, стеку Р,, полученному в результате выполнения 1-й операции, соответствует неотрицательный потенциал; следовательно, Ф (Р;) > 0 = Ф(Ро) . Таким образом, полная амортизнрованная стоимость п операций, связанная с функцией Ф, представляет собой верхнюю границу фактической стоимости.
Теперь вычислим амортизированные стоимости различных стековых операций. Если 1-я операция над стеком„содержащим з объектов, — операция Ризи, то разность потенциалов равна Ф(Р;) — Ф(Р, 1) = (а+ 1) — а = 1. Согласно уравнению (17.2), амортизированная стоимость операции Ризи равна ~ =,+Ф(Р;) — Ф(Р;,) =1+1=2. Глава 17. Амортизационный анализ 493 Предположим, что г-я операция над стеком — операция М~лтпчзе(Я, й), и что из него извлекается й' = ппп (й, в) объектов.
Фактическая стоимость этой операции равна Й', а разность потенциалов— Ф(О;) — Ф(зЭ; 1) = — lс'. Таким образом, амортизированная стоимость операции Мсьт|еоР равна с; = с, +Ф(О;) — Ф(О; 1) = 1С вЂ” й = О. Аналогично можно показать, что амортизированная стоимость операции Рок также равна О. Амортизированная стоимость каждой из трех операций равна О (1), поэтому полная амортизированная стоимость последовательности из 7з операций равна О (и). Мы уже доказали, что Ф (.0;) > Ф (Оо), поэтому полная амортизированная стоимость и операций является верхней границей полной фактической стоимости.
Поэтому в наихудшем случае стоимость п операций равна О (и). Увеличение показаний бинарного счетчика В качестве другого примера метода потенциалов снова обратимся к задаче о приращении показаний бинарного счетчика. На этот раз определим потенциал счетчика после выполнения 1-й операции 1нскемент как количество Ь; содержа- шихся в счетчике единиц после этой операции. Вычислим амортизированную стоимость операции 1ХСКЕМЕХТ. Предположим, что г-я операция 1мскемемт обнуляет Ц битов.
В таком случае фактическая стоимость этой операции не превышает значения Ц + 1, поскольку вдобавок к обнулению Ц битов значение 1 присваивается не более чем одному биту. Если Ь; = О, то в ходе выполнения 1-й операции обнуляются все 1с битов, так что Ь; 1 = 1; = к. Если Ь; > О, то выполняется соотношение Ь; = Ь; г — Ц + 1. В любом случае, справедливо неравенство Ь; < Ь; 1 — 1; + 1 и разность потенциалов равна Ф (111) Ф(11а-г) ~ ~(Ь1-з н+ 1) Ь1-1 = 1 н. Таким образом, амортизированная стоимость определяется соотношением с; = с, + Ф(В;) — Ф(Рз 1) ( (1;+ 1) +(1 — 1;) = 2.
Если вначале показания счетчика равны нулю, то Ф (.Оо) = О. Поскольку при всех 1 справедливо неравенство Ф (.0;) > О, то полная амортизированная стоимость последовательности из и операций 1НСКЕМЕНТ является верхней границей полной фактической стоимости, поэтому в наихудшем случае стоимость и операций 1нскемент равна О (и). Часть И. Усовершенствованные методы разработки и анализа 494 Метод потенциалов предоставляет простой способ анализа счетчика даже в том случае, когда отсчет начинается не с нуля.
Пусть изначально показание счетчика содержит Ье единиц, а после выполнения и операций 1нскпмнчт — Ь„ единиц, где О < Ьо,Ь„ < й.(Напомним, что й — количество битов в счетчике.) Тогда уравнение (17.3) можно переписать следующим образом: и И ~';= ~'Е-Ф(Р„)+Ф(Ро). (17.4) а=1 При всех 1 < 1 < и выполняется неравенство с; < 2. В силу соотношений Ф (Ро) = Ьо и Ф (.0„) = Ь„полная фактическая стоимость п операций 1нскпмент равна в ь с~ ( (~) 2 Ьп + Ьв = 2п Ьи + Ьо. В частности, заметим, что поскольку Ье < й, то при й = О (п) полная фактическая стоимость равна О (и). Другими словами, если выполняется не менее и = й(й) операций 1нскпмнчт, полная фактическая стоимость независимо от начального показания счетчика равна О (п).
17.3-5. Предположим, что изначально показание счетчика не равно нулю, а определяется числом, содержащим в двоичном представлении Ь единиц. Покажите, что стоимость выполнения п операций 1нскпмент равна О (и) при условии, что и = П (Ь). (Не следует предполагать, что Ь вЂ” константа,) Упражнения 17.3-1. Предположим, задана такая потенциальная функция Ф, что при всех 1 выполняется неравенство Ф (Р;) > Ф (Ро), но Ф (Ро) ф О. Покажите, что существует потенциальная функция Ф' такая, что Ф' (.Ро) = О и Ф' (Р;) > > О для всех г > 1, и соответствующая функции Ф' амортнзированная стоимость такая же, как и для функции Ф.
17.3-2. Еще раз выполните упражнение 17.1-3 с помощью метода потенциалов. 17.3-3. Рассмотрим и-элементную бинарную неубывающую пирамиду. Пусп в этой структуре данных поддерживаются операции 1нзект и Ехтклст Мпч, для выполнения которых в наихудшем случае требуется время О (1яп). Определите потенциальную функцию Ф такую, что амортизированная стоимость операции 1нзпкт равна О (1я и), а амортизированная стоимость операции Ехтклст М~н — О (1), и покажите, что она работает. 17.3-4. Чему равна полная стоимость выполнения и стековых операций Роьн, Рор и Мгл.тп'ов, если предположить, что в начале стек содержит зе объектов, а в конце — з„объектов? Глава 17.
Амортизационный анализ 495 17.3-6. Покажите, как реализовать очередь на основе двух обычных стеков (см. упражнение 10.1-6) таким образом, чтобы амортизированная стоимость каждой из операций Ен00Б1к и 13е00иик была равна О (1). 17.3-7. Разработайте структуру данных для поддержки следующих двух операций над динамическим множеством целых чисел Я: 1хзккт(Я, х) — вставка объекта х в Я; Пкьктк 1.лкскк НА1.г(Я) — удаление ПЯ~/2) наибольших элементов из множества Я. Поясните, как реализовать эту структуру данных, чтобы любая последовательность из т операций выполнялась за время О (т).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
