Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 107
Текст из файла (страница 107)
Теперь добавим к стеку операцию Мо1.т1рОр(5, л), снимающую й объектов (или все оставшиеся, если всего их меньше, чем Й) с вершины стека Я . В приведенном ниже псевдокоде операция Ятлск-Емрту возвращает значение ткал, Пзава )Х Амортизационный анализ 489 (ор -м 23 17 6 39 1О 47 (ор-м 1О 47 (в) (б) (в) Рис. 17.1. Работа процедуры Мцьт)гог со стеюм Я, начальное состояние матерого показано а части (а).
Процедура Мшт)гог(5, 4) снимает со стека верхние четыре объекта, после чего стек принимает вид, показанный в части (б). Очередная операция, Мсьт(гок(5, 7), опустошает стек, как показано в части (в), поскольку перед ней в стеке оставалось менее семи объектов. если в данный момент в стеке нет объектов, и значение Рдьбн — в противном случае. М~Л.Т1РОР(5, )с) 1 )к))йе Ятдск-Емрту(Я) == Едете и и > О 2 РОР(з') 3 )с=)с — 1 На рис. 17.! показан пример работы процедуры М()ЕТ(РОР.
В течение какого времени операция МЛ.Т)РОР(Я, )с) выполняется над стеком, содержащим л объектов? Фактическое время работы линейно зависит от количества реально выполняемых операций РОР, поэтому достаточно проанализировать процедуру МЛ.Т1РОР в терминах абстрактных единичных стоимостей каждой из операций РОзн и РОР. Количество итераций цикла чгЫ1е равно количеству пцп(л, )с) объектов, снимаемых со стека. При каждой итерации в строке 2 выполняется однократный вызов процедуры РОР.
Таким образом, полная стоимость процедуры М()ет)РОР равна ш)п(л, к), а фактическое время работы является линейной функцией от этой величины. Теперь проанализируем последовательность операций Рпбн, РОР и Мщ.т(РОР, действующих на изначально пустой стек. Стоимость операции МЛ.Т(РОР в наихудшем случае равна О(п), поскольку в стеке не более и объектов. Таким образом, время работы любой стековой операции в наихудшем случае равно О(п), поэтому стоимость последовательности и операций равна О(пз), так как зта последовательность может содержать 0(п) операций М() ет) ОР, стоимость каждой из которых равна 0(п). Но несмотря на то что анализ проведен правильно, результат 0(п ), полученный при рассмотрении наихудшей стоимости каждой операции в отдельности, является слишком грубым.
С помощью группового анализа можно получить более точную верхнюю границу при рассмотрении совокупной последовательности и операций. Фактически, хотя одна операция М()ьт)РОР может быть весьма дорогостоящей, стоимость произвольной последовательности, состоящей из п операций Р()зн, РОР и М(л.т(РОР, которая выполняется над изначально пустым стеком, не превышает 0(п). Почему? Потому что каждый помещенный в стек объект можно извлечь оттуда не более одного раза. Таким образом, число вызовов операций РОР (вкпю- 490 Часть 1Л усовершенствованные методы равработли и анализа чая их вызовы в процедуре М~л.т!909) для иепустого стека не может превышать количество выполненных операций Рози, которое, в свою очередь, не больше п. При любом п для выполнения произвольной последовательности из п операций Розн, Рог и М~л.тп'ог требуется суммарное время 0(п). Таким образом, средняя стоимость операции равна 0(п)7п = 0(1).
В групповом анализе амортизированная стоимость каждой операции принимается равной ее средней стоимости, поэтому в данном примере все три стековые операции характеризуются амортизированной стоимостью, равной О(1). Еще раз стоит заметить, что хотя только что было показано, что средняя стоимость (а следовательно, и время выполнения) стековой операции равна О(1), при этом не делалось никаких вероятностных рассуждений.
Фактически была найдена граница времени выполнения последовательности из и операций в наихудшем случае, равная О(п). После деления этой полной стоимости на п получается средняя стоимость одной операции, или амортизированная стоимость. Увеличение показаний бинарною счетчика В качестве другого примера группового анализа рассмотрим задачу реализации !с-битового бинарного счетчика, который ведет счет от нуля в восходящем направлении. В качестве счетчика используется битовый массив А[О .. !с — Ц, где А.
1епдгл = /с. Младший бит храняшегося в счетчике бинарного числа х находится в элементе А[0], а старший бит — в элементе А[й — 1], так что х = 2 ~ о~ А[1].2*. Изначально х = О, т.е. А[1] = О для! = О, 1,..., /с — 1. Чтобы увеличить показания счетчика на 1 (по модулю 2"), используется следующая процедура. 1нсклмлнт(А) 1 !=О 2 звЫ1е1 < А.!епдс!ь и А[1] == 1 3 А[1] =О 4 1=1+1 5 Ы1 < А.!епдс)ь б А[1] =1 На рис. 17.2 показано, что происходит в бинарном счетчике при его увеличении 16 раз. В начале каждой итерации цикла знЬПе в строках 2-4 мы добавляем 1 к биту в позиции 1.
Если А[1] = 1, то добавление 1 обнуляет бит, который находится на позиции 1, и приводит к тому, что добавление 1 будет выполнено и в позиции 1+ 1 на следующей операции цикла. В противном случае цикл оканчивается, так что если по его окончании ! < к, то А[в] = О и нам нужно изменить значение 1-го бита на 1, что и делается в строке 6. Стоимость каждой операции 1нсклмлнт линейно зависит от количества измененных битов.
Как и в примере со стеком, поверхностный анализ даст правильную, но неточную оценку. В наихудшем случае, когда массив А состоит только из единиц, для выполнения операции 1нсклмлнт потребуется время 0(к). Таким образом, выполнение последовательности из п операций 1нсклмлмт для изначально обнуленного счетчика в наихудшем случае займет время О(пк). Глава 12 Амортизационный анализ 491 Значенне сччтчннн Рис.
17.2. 8-битовый бинарный счетчик. знечение мпорого увелнчиваегся с 0 до 16 с помощью 16 операций !нскнмннт. Бнпя, значения которых изменяются прн переходе к следующему значению, заштрихованы. Справа приведена стоимость, требуемая для изменения битов. Обратите внимание, по полная стоимость никогда более чем в два раза не превышает общего количества операций !Искемеит. Этот анализ можно уточнить, в результате чего для последовательности из и операций 11чскбмнчт в наихудшем случае получается стоимость 0(п).
Такая оценка вгпможна благодаря тому, что далеко не при каждом вызове процедуры 1нсйбмб!4т изменяются значения всех битов. Как видно из рис. 17.2, элемент А[0[ изменяется при квкдом вызове операции 11чскбмп1чт. Следующий по старшинству бвт А[1[ изменяется только через раз, так что последователъность из п операций 1!40кбы81чт над изначально обнуленным счетчиком приводит к изменению элемента А[1[ [п/21' рвэ. Аналогично бит А[2] изменяется только каждый четвертый раз, т.е. [п/41 раз в последовательности из п операций 1!чскбм81чт над изначально обнуленным счетчиком. В общем случае для з = О, 1,..., 7с — 1 бит А[а[ изменяется [п/2!1 раз в последовательности из гг операций 11чскпм81чт над изначально обнуленным счетчиком. Биты же в позициях з ) и не изменяются.
Таким образом, общее количество изменений битов при выполнении последовательности операций равно а-1 оо кР1 "И г=о ч=с согласно уравнению (А.б). Поэтому время выполнения последовательности из п операций 1зчскбмбзят над изначально обнуленным счетчиком в наихудшем слу- чае равно 0(п). Средняя стоимость каждой операции, а следовательно, и амор- тизированная стоимость операции, равна О(п)/п = 0(1). 0 1 2 3 4 5 6 7 8 9 10 11 12 !3 14 15 !6 бч,йбч,ьччбчф,~~ф 0000000ий О О О О О О йй15 000000 1йй о о о о о ч(гййв!(л) 0 0 0 0 0 1 0'8$ о о о о о 1йб~И 000001 1йй о о о оййФФМ',!~!з 00001ООййз 000010ййй 0000101йй оооо!йВФййй 00001!ОФ 000011йййй оооо!11йй О 0 О К4МййВФ 0001000цй О 1 3 4 7 8 10 11 15 16 18 19 22 23 25 26 31 Часть Я Усовершенствованные методы разработки и анавиза 492 Упражнения 17.1.1 Остается ли справедливой оценка амортизированной стоимости стековых операций, равная 0(1), если включить в множество стековых операций операцию Мпьтшпзн, помещающую в стек й элементов? 17.1.2 Покажите, что если бы в пример с й-битовым счетчиком была включена операция Рескеыемт, стоимость зз операций была бы равной сЭ(п(с).
17.1.3 Предположим, что над структурой данных выполняется п операций. Стоимость (-й по порядку операции равна (, если ( — это точная степень двойки, и 1 — в противном случае. Определите с помощью группового анализа амортизированную стоимость операции. 17.2. Метод бухгалтерского учета В меязоде бухгазпяерского учета (ассоппйпд шейзод), применяемом в ходе группового анализа, разные операции оцениваются по-разному, в зависимости от их фактической стоимости.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
