Алгоритмы - построение и анализ (1021735), страница 98
Текст из файла (страница 98)
Амортизационный анализ 483 В разделе 17.3 обсуждается метод потенциалов, напоминающий метод бухгалтерского учета в том отношении, что в нем определяется амортизированная стоимость каждой операции, причем стоимость ранних операций последовательности может переоцениваться, чтобы впоследствии компенсировать заниженную стоимость более поздних операций.
В методе потенциалов кредит поддерживается как "потенциальная энергия" структуры данных в целом, а не связывается с отдельными объектами этой структуры данных. Все трн перечисленных метода будут опробованы на двух примерах. В одном из них рассматривается стек с дополнительной операцией Миьт1гог, в ходе выполнения которой со стека одновременно снимается несколько объектов.
Во втором примере реализуется бинарный счетчик, ведущий счет от нуля при помощи единственной операции — 1хскемечт. В ходе чтения этой главы следует иметь в виду, что при выполнении амортизационного анализа расходы начисляются только для анализа алгоритма, и в коде в них нет никакой необходимости. Например, если при использовании метода бухгалтерского учета обьекту з приписывается какой-нибудь кредит, то в коде не нужно присваивать соответствующую величину некоторому атрибуту стеНЫ 1я). Глубокое понимание той или иной структуры данных, возникающей в ходе амортизационного анализа, может помочь оптимизировать ее устройство.
Например, в разделе 17.4 с помощью метода потенциалов проводится анализ динамически увеличивающейся и уменьшающейся таблицы. 17.1 Групповой анализ В ходе группового аиализа (а88гейаге ала1уз1з) исследователь показывает, что в наихудшем случае общее время выполнения последовательности всех и операций в сумме равно Т (и). Поэтому в наихудшем случае средняя, или амортизированная, стоимость (ашог11хед соз1), приходящаяся на одну операцию, определяется соотношением Т (и)/и. Заметим, что такая амортизированная стоимость применима ко всем операциям, даже если в последовательности они представлены несколькими типами. В других двух методах, которые изучаются в этой главе,— методе бухгалтерского учета и методе потенциалов — операциям различного вида могут присваиваться разные амортизированные стоимости.
Стековые операции В качестве первого примера группового анализа рассматриваются стеки, в которых реализована дополнительная операция. В разделе 10.1 представлены две основные стековые операции, для выполнения каждой из которых требуется вре- мя 0(1): Часть 1Ч. Усовершенствованные методы разработки н анализа 484 )ор -~ 23 !7 6 39 )О 47 1ор -в 1О 47 б) в) в) Рис.
17.1. Действие операции М)л.тп'ор ная стеком Я Р))зн(Я, х) добавляет объект х в стек Я; Рор(Я) извлекает обьект с вершины стека Я и возвращает его. Поскольку каждая из этих операций выполняется в течение времени О(1), примем их длительность за единицу. Тогда полная стоимость последовательности, состоящей из 77 операций Р))ЗН и Рор, равна и, а фактическое время выполнения п таких операций — )В (п). Теперь добавим к стеку операцию Мя;прор(Я, )о), извлекающую с вершины стека Я 19 обьектов (или все оставшиеся, если всего их меньше, чем 14).
В приво денном ниже псевдокоде операция БтАск Емрту возвращает значение ти)е, если в данный момент в стеке нет объектов, и значение Рл~.зп в противном случае: М)~.Т)РОР(Я, )о) 1 ттййе Бтлск Емрту(Я) ~ Рмлни Й ФО 2 йо РОР(Я) 3 к+- /с — 1 Пример работы операции М))ьт)рор проиллюстрирован на рис. 17.1. На рис.
17.1а показано начальное состояние стека. В результате выполнения операции МП.Т1- Рор(Я, 4) извлекаются верхние 4 объекта (см. рис. 17.1 б). Следующая операция— М)л.т)Р0Р(5,7). Она опустошает стек, поскольку в нем осталось меньше семи объектов. Результирующее состояние стека показано на рис. 17.1в. В течение какого времени операция М~й:прор(Я, )о) выполняется нал стеком, содержащем а обьектов? Фактическое время работы линейно зависит от количества реально выполняемых операций Р0Р, поэтому достаточно проанализировать процедуру Мш.т)рор в терминах абстрактных единичных стоимостей каждой из операций Ризи и Р0Р.
Количество итераций цикла и Ьйе равно количеству ппп (а, )о) объектов, извлекаемых из стека. При каждой итерации в строке 2 выполняется однократный вызов процедуры Рор. Таким образом, полная стоимосп процедуры М)л.т1Р0Р равна пнп (а, к), а фактическое время работы является линейной функцией от этой величины. Глава 17. Амортизационный анализ 485 Теперь проанализируем последовательность операций Ризи, РоР и Мгл.т1РоР, действующих на изначально пустой стек. Стоимость операции МБ~.ТЕРРОР в наихудшем случае равна 0 (и), поскольку в стеке не более и объектов.
Таким образом, время работы любой стековой операции в наихудшем случае равно О (и), поэтому стоимость последовательности и операций равна 0 (из), так как эта последовательность может содержать 0 (и) операций М~л.ТЕРРОР, стоимость каждой из которых равна 0 (и). Но несмотря на то, что анализ проведен правильно, результат 0 [из), полученный при рассмотрении наихудшей стоимости каждой операции в отдельности, является слишюм грубым. С помощью группового анализа можно получить более точную верхнюю границу при рассмотрении совокупной последовательности и операций.
Фактически хотя одна операция Мы.Т~РоР может быть весьма дорогостоящей, стоимость произвольной последовательности„состоящей из и операций РОзн, РОР и Ми~.Т~РоР, юторая выполняется над изначально пустым стеком, не превышает О(и). Почему? Потому что каждый помещенный в стек объект можно извлечь оттуда не более одного раза. Таким образом, число вызовов операций РоР (включая их вызовы в процедуре М~Л.Т!РОР) для непустого стека не может превышать количество выполненных операций Ризн, которое, в свою очередь, не больше и. При любом и для выполнения произвольной последовательности из и операций Ризи, РоР и Мцьт1РоР требуется суммарное время 0 (и). Таким образом, средняя стоимость операции равна 0 (и)/и = 0 (1). В групповом анализе амортизированная стоимость каждой операции принимается равной ее средней стоимости, поэтому в данном примере все три стековые операции характеризуются амортизированной стоимостью, равной 0 (1).
Еще раз стоит заметить, что хотя только что было показано, что средняя стоимость (а следовательно, и время выполнения) стеювой операции равна 0 (1), при этом не делалось никаких вероятностных рассуждений. Фактически была найдена граница времени выполнения последовательности из и операций в наихудшем случае, равная 0 (и). После деления этой полной стоимости на и получается средняя стоимость одной операции, или амортизированная стоимость. Приращение показаний бинарного счетчика В качестве другого примера группового анализа рассмотрим задачу о реализации й-битового бинарного счетчика, который ведет счет от нуля в восходящем направлении. В качестве счетчика используется битовый массив А [О..к — 1], где 1еидгй [А] = й.
Младший бит хранящегося в счетчике бинарного числа х находится в элементе А [О], а старший бит — в элементе А [й — 1], так что х = = 2 ~ о А [1] 2 . Изначально х = О, т.е. А [г] = 0 для г = О, 1,..., 1с — 1. Чтобы увеличить показания счетчика на 1 (по модулю 2"), используется приведенная ниже процедура: Часть !Ч. Усовершенствованные методы разработки н анализа 486 Звассвсс сссв!нкс Обсвя сссссос! Рис. 17.2. Бинарный 8-батовый счетчик в процессе изменения его значения от О до 16 операцией 1НСКЕМЕНт 1!чскемехт(А) ! ! — О 2 5чй!!е ! < !епд!6[А] и А[!] = 1 з 6!о А[!] О 4 ! -!+1 5 !Г ! < !епдОЬ[А] 6 т!зеп А[!] с- 1 На рис. 17.2 показано, что происходит в бинарном счетчике при его увеличении 16 раз. Биты, значения которых изменяются при переходе к следующему этапу, заштрихованы.
Справа приведена стоимость, требуемая для изменения битов. Обратите внимание, что полная стоимость никогда более чем в два раза не превышает общего количества операций 1нскемент. При этом показания счетчика возрастают от О до 16. В начале каждой итерации цикла зтййе в строках 2-4 мы добавляем 1 к биту в позиции г. Если А [!] = 1, то добавление 1 обнуляет бит, который находится на позиции г, и приводит к тому, что добавление 1 будет выполнено и в позиции ! + 1, на следующей операции цикла.
В противном случае цикл оканчивается, так что если по его окончании ! < !О, то А [!] = О и нам надо изменить значение 1-го бита на 1, что и делается в строке 6. Стоимость каждой операции 110скемемт линейно зависит от количества измененных битов. Как и в примере со стеком, поверхностный анализ даст правильную, но неточную оценку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
