Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 108
Текст из файла (страница 108)
Величина, которая начисляется на операцию, называется амортиэированной стоимостью (ашогбгед созг). Если амортизированная стоимость операции превышает ее фактическую стоимость, то соответствующая разность присваивается определенным объектам структуры данных как кредияз (сгес(й). Кредит можно использовать впоследствии для компенсирующих выплат на операции, амортизированная стоимость которых меньше их фактической стоимости. Таким образом, можно полагать, что амортизированная стоимость операции состоит из ее фактической стоимости и кредита, который либо накапливается, либо расходуется. Этот метод существенно отличается от группового анализа, в котором все операции характеризуются одинаковой амортизированной стоимостью.
К выбору амортизированной стоимости следует подходить с осторожностью. Если нужно провести анализ с использованием амортизированной стоимости, чтобы показать, что в наихудшем случае средняя стоимость операции невелика, полная амортизированная стоимость последовательности операций должна быть верхней границей полной фактической стоимости последовательности. Более того, как и в групповом анализе, это соотношение должно соблюдаться для всех последовательностей операций. Если обозначить фактическую стоимосты-й операции через с,„а аморгизированную стоимость зъй операции через с„то указанное требование для всех последовательностей, состоящих из и операций, можно Глаеа! Х Амортизацчонцый аиялиз 493 выразить следующим образом: ~с,>~ с,. (17.1) Общий кредит, хранящийся в структуре данных, представляет собой разность между полной амортизированной стоимостью и полной фактической стоимостью, или 2',".
1 с, — 2," с;. Согласно неравенству (17.1) полный кредит, связанный со структурой данных, все время должен быть неотрицательным. Если бы полный кредит в каюм-либо случае мог стать отрицательным (в результате недооценки ранних операций с надеждой восполнить счет впоследствии), то полная амортизнрованная стоимость в тот момент была бы ниже соответствующей фактической стоимости; значит, для последовательности операций полная амортизированная стоимость не была бы в зтот момент времени верхней границей полной фактичесюй стоимости. Таким образом, необходимо позаботиться о том, чтобы полный кредит для структуры данных никогда не становился отрицательным. Стековые операции Чтобы проиллюстрировать, как проводится амортизационный анализ методом бухгалтерского учета, вернемся к примеру со стеюм.
Напомним, что фактическая стоимость операций была следующей: Рпзн 1, РОР 1, М$Л.Т!РОР ппп()с, а) где /с — аргумент процедуры М~л.т19ор, а а — размер стека в момент ее вызова. Присвоим приведенные ниже амортизированные стоимости: Рпзн 2, РОР О, М1Л.Т!РОР 0 . Заметим, что амортизированная стоимость операции Мпьт19ОР равна константе (О), в то время как ее фактическая стоимость — переменная величина.
В атой схеме все три амортизированные стоимости равны 0(1), хотя в общем случае асимптотичесюе поведение аморгизированных стоимостей рассматриваемых операций может быть разным. Теперь покажем, что любую последовательность стековых операций можно оплатить путем начисления амортизированных стоимостей. Предположим, что для представления каждой единицы затрат используется денежный счет. Пусть изначально стек пуст. Вспомним аналогию между стеком как структурой данных и стопкой тарелок в кафетерии, приведенную в разделе 10.1. При добавлении тарелки в стопку 1 доллар затрачивается на оплату самой операции добавления, а еще 1 доллар (из двух начисленных на операцию Рпзн) остается в запасе, как бы иа зтой тарелке.
В любой момент времени каждой тарелке стека соответствует 1 доллар кредита. Хранящийся в тарелке 1 доллар предназначен для оплаты стоимости ее извлечения из стека. На операцию РО9 ничего не начисляется, а ее фактическая 494 ггастл ГК 'Усовершенствованные методы разработки и анагиза стоимость выплачивается за счет кредита, который хранится в стеке. При извлечении тарелки изымается 1 доллар кредита, который используется для оплаты фактической стоимости операции.
Таким образом, благодаря небольшой переоценке операции Рпзн отпадает необходимость начислять какую-либо сумму на операцию РОЕ. Более того, на операцию Мпет19ОЕ также не нужно начислять никакой суммы. При извлечении первой тарелки мы берем из нее 1 доллар кредита и тратим его на оплату фактической стоимости операции РОЕ. При извлечении второй тарелки в ней также есть 1 доллар кредита на оплату фактической стоимости операции Рог и т.д. Таким образом, начисленной заранее суммы всегда достаточно для оплаты операций Мш.тшОЕ. Другими словами, поскольку с каждой тарелкой стека связан 1 доллар кредита и в стеке всегда содержится неотрицательное количество тарелок, можно быть уверенным, что сумма кредита всегда неотрицательна.
Таким образом, для любой последовательности из п операций РОЗН, РОЕ и Мцьт19ог полная амортизированная стоимость является верхней границей полной фактической стоимости. Поскольку полная амортизированная стоимость равна 0(п), полная фактическая стоимость также определяется этим значением. Увеличение показаний бинарного счетчика В качестве другого примера, иллюстрирующего метод бухгалтерского учета, проанализируем операцию 1нсаемемт, которая выполняется над бинарным изначально обнуленным счетчиком. Ранее мы убедились, что время выполнения этой операции пропорционально количеству битов, изменяющих свое значение, В данном примере это количество используется в качестве стоимости.
Как и в предыдущем примере, для представления каждой единицы затрат (в данном случае— изменения битов) будет использован денежный счет. Чтобы провести амортизационный анализ, начислим на операцию, при которой биту присваивается значение 1 (т.е. бит устанавливается), амортизированную стоимость, равную 2 долларам. Когда бит устанавливается, 1 доллар (из двух начисленных) расходуется на оплату операции по самой установке. Оставшийся 1 доллар вкладывается в этот бит в качестве кредита для последующего использования при его обнулении. В любой момент времени с каждой единицей содержащегося в счетчике значения связан 1 доллар кредита, поэтому для обнуления бита нет необходимости начислять какую-либо сумму; за сброс бита достаточно будет уплатить 1 доллар.
Теперь можно определить амортизированную стоимость операции 1нспемемт. Стоимость обнуления битов в цикле гна11е выплачивается за счет тех денег, которые связаны с этими битами. В процедуре 1мспеме1чт устанавливается не более одного бита (в строке б), поэтому амортизированная стоимость операции 11чскемеыт не превышает 2 долларов. Количество единиц в бинарном числе, представляющем показания счетчика, не может быть отрицательным, поэтому и сумма кредита всегда неотрицательна. Таким образом, Глава 77. Амортизационный аиивиз 495 полная амортизированная стоимость п операций 1хскемехт равна 0(п).
Это и есть оценка полной фактической стоимости. Упражнения 172.1 Предположим, что над стеком выполняется последовательность операций; размер стека при этом никогда не превышает )в. После каждых й операций проводится резервное копирование стека. Присвоив различным стековым операциям соотвегствуклцие амортизированные стоимости, покажите, что стоимость и стековых операций, включая копирование стека, равна 0(п). 17.22 Выполните упр. 17.1.3, применив для анализа метод бухгалтерского учета. 17.2.3 Предположим, что нам нужно иметь возмохсность не только увеличивать показания счетчика, но и сбрасывать его (т.е. делать так, чтобы значения всех битов были равны 0).
Считая, что время проверки или модификации одного бита составляет 6(1), покажите, как осуществить реализацию счетчика в виде массива битов, чтобы для выполнения произвольной последовательности из и операций !нскемент и Кезет над изначально обнуленным счетчиком потребовалось бы время 0(п). (Указание: отслеживайте в счетчике самый старший разряд, содержащий единицу.) 17.3.
Метод потенциалов Вместо представления предоплаченной работы в виде кредита, хранящегося в структуре данных вместе с отдельными объектами, в ходе амортизированного анализа по метедуз нетенцнелее (рогепба1 шейзоб) такая работа представляется в виде "потенциальной энергии", или просто "потенциала", который можно высвободить для оплаты последующих операций. Этот потенциал связан со структурой данных в целом, а не с ее отдельными объектами. Метод потенциалов работает следующим образом. Мы начинаем с исходной структуры данных Ро, над которой выполняется и операций.
Для всех з = 1, 2,..., п обозначим через с, фактическую стоимосты-й операции, а через Р; — структуру данных, которал получается в результате применения з-й операции к структуре данных Р, ъ Функция потенциале (рогепйа1 йшсйоп) Ф отображает каждую структуру данных Р; на действительное число Ф(Р,), которое является нотенцнааан (ро1епйа!), связанным со структурой данных Р;. Аморавзнреееннея стонзность (азпогбхео соз!) с, з-й операции определяется соотношением с, = с, + Ф(Р,) — Ф(Р, г) (17.2) Часть ги Усовершенствованные методы разработки н аназиза 49б Таким образом, амортизированная стоимость каждой операции представляет со- бой ее фактическую стоимость плюс приращение потенциала в результате выпол- нения операции. Согласно уравнению (17.2) полная амортизированная стоимость и операций равна и н с; = ~~(с, + Ф(Р;) — Ф(Р, 1)) ь=1 з=1 = ~~',с + Ф(Рн) — Ф(Ро) з=1 (17.3) Стековые операции Чтобы проиллюстрировать метод потенциалов, еще раз обратимся к примеру со стековыми операциями Рахн, Рог и Мцьт19ор.
Определим функцию потенциала Ф для стека как количество объектов в этом стеке. Для пустого стека Ро, с которого мы начинаем, выполняется соотношение Ф(Ро) = О. Поскольку количество объектов в стеке не может быть отрицательным, стеку Р„полученному в результате выполнения з-й операции, соответствует неотрицательный Второе равенство следует из уравнения (А.9), поскольку слагаемые Ф(Р1) являются телескопическими. Если функцию потенциала Ф можно определить таким образом, чтобы выполнялось неравенство Ф(Р„) > Ф(Рр), то полная амортизированная стоимость 2„'," 1с; является верхней границей полной фактической стоимости 2'," сь На практике не всегда известно, сколько операций может быть выполнено, поэтому, если наложить условие Ф(Р,) > Ф(Ро) для всех з, то, как и в методе бухгалтерского учета, будет обеспечена предоплата. Часто удобно определить величину Ф(Ре) равной нулю, а затем показать, что для всех з выполняется неравенство Ф(Р1) ) О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
