Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 100
Текст из файла (страница 100)
В разделе 17.2 описывается метод бухгалтерского учета, в котором определяется амортизированная стоимость каждой операции. Если имеется несколько видов операций, то каждый из них может характеризоваться своей амортизированной стоимостью. В этом методе стоимость некоторых операций, находящихся в начальной части последовательности, может переоцениваться. Эта переоценка рассматривается как своего рода "предварительный кредит" для определенных объектов структуры данных. Впоследствии такой кредит используется для "оплаты" тех операций последовательности, которые оцениваются ниже, чем стоят на самом деле.
Глава 17. Амортизационный анализ 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!о А[6] О 4 ! -!+1 5 !Г ! < !епдОЬ[А] 6 т!зеп А[!] +- 1 На рис. 17.2 показано, что происходит в бинарном счетчике при его увеличении 16 раз. Биты, значения которых изменяются при переходе к следующему этапу, заштрихованы. Справа приведена стоимость, требуемая для изменения битов. Обратите внимание, что полная стоимость никогда более чем в два раза не превышает общего количества операций 1нскнмнчт.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
