Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 101
Текст из файла (страница 101)
При этом показания счетчика возрастают от О до 16. В начале каждой итерации цикла зтййе в строках 2-4 мы добавляем 1 к биту в позиции г. Если А [!] = 1, то добавление 1 обнуляет бит, который находится на позиции г, и приводит к тому, что добавление 1 будет выполнено и в позиции ! + 1, на следующей операции цикла. В противном случае цикл оканчивается, так что если по его окончании ! < !О, то А [!] = О и нам надо изменить значение 1-го бита на 1, что и делается в строке 6.
Стоимость каждой операции 110скемемт линейно зависит от количества измененных битов. Как и в примере со стеком, поверхностный анализ даст правильную, но неточную оценку. В наихудшем случае, когда массив А состоит только из единиц, для 0 1 5 4 6 7 5 1! !О ;* О 16 !5 !6 о 0 0 о 0 о О!!6! О 0 О 0 0!О!М!Ос 0000001йф О 0 0 о"'Фссй28 0 О 0 !! 103~ 0 0 0 О 0 1сйе51! 0 О 0 0 0 ! 1ВО! 0 О О 0!ЗФ$й4жЗ 0 00 01005:;01 0 0 0 О ! О!бай 0 0 0 О ! О !.':81 О 0 О 1 ! !5 Д! 0 О 0 О 1 !Вйй 0 П 0 0 ! 1 ! 161 о О О !ЙЗЯЙГйн!!Н 0 00 1 О !50НЧ ! 5 10 11 15 16 ~5 19 00 05 26 Глава 17. Амортизационный анализ 487 выполнения операции 1мскемнчт потребуется время 9 (й).
Таким образом, выполнение последовательности из и операций 1хскемемт для изначально обнуленного счетчика в наихудшем случае займет время О (ик). Этот анализ можно уточнить, в результате чего для последовательности из и операций 1мскемент в наихудшем случае получается стоимость О (и). Такая оценка возможна благодаря тому, что далеко не при каждом вызове процедуры 1мскемичт изменяются значения всех битов. Как видно из рис.
17.2, элемент А [0] изменяется при каждом вызове операции 1ХСКЕМЕХт. Следующий по старшинству бит А [1] изменяется только через раз, так что последовательность из и операций 1МСКЕМЕМт над изначально обнуленном счетчиком приводит к изменению элемента А [1] [и/2] раз. Аналогично, бит А [2] изменяется только каждый четвертый раз, т.е. ~и/4] раз в последовательности из и операций 1~чскемент над изначально обнуленном счетчиком. В общем случае, для 1 = О, 1,..., 1с — 1, бит А [г] изменяется [и/2'] раз в последовательности из и операций 1МСКЕМЕЫт в изначально обнуленном счетчике.
Биты же на позициях г > (с не изменяются. Таким образом, общее количество изменений битов при выполнении последовательности операций равно ь-1 ОО ,'~ Ц <и~) —,=2и 1=0 з=о (см. уравнение (А.б)). Поэтому время выполнения последовательности из и операций 1мскем~чт над изначально обнуленном счетчиком в наихудшем случае равно О (и). Средняя стоимость каждой операции, а следовательно, и амортизированная стоимость операции, равна О (и)/и = О (1). Упражнения 17.1-1. Остается ли справедливой оценка амортизированной стоимости стековых операций, равная О (1), если включить в множество стековых операций операцию Мшт~Рцзн, помещающую в стек Й элементов? 17.1-2.
Покажите, что если бы в пример с к-битовым счетчиком была включена операция 1)ЕСКЕМЕХт, стоимость и операций была бы равной 9 (ий). 17.1-3. Над структурой данных выполняется и операций. Стоимость г-й по порядку операции равна г, если г — это точная степень двойки, и 1 в противном случае. Определите с помощью группового анализа амортизированную стоимость операции. 17.2 Метод бухгалтерского учета В методе бухгалтерского учета (ассошцш8 шебзоб), применяемом при групповом анализе, разные операции оцениваются по-разному, в зависимости от их Часть 1Ч.
Усовершенствованные методы разработки и анализа 488 фактической стоимости. Величина, которая начисляется на операцию, называется амортизировапной стоимостью (ашог11геб созГ). Если амортизированнзя стоимость операции превышает ее фактическую стоимость, то соответствующая разность присваивается определенным объектам структуры данных как кредиа (сгедп). Кредит можно использовать впоследствии для компенсирующих выплат на операции, амортизированная стоимость которых меньше их фактической стоимости.
Таким образом, можно полагать, что амортизированная стоимость опера. ции состоит из ее фактической стоимости и кредита, который либо накапливается, либо расходуется. Этот метод значительно отличается от группового анализа, в котором все операции характеризуются одинаковой амортизированной стоимостью. При выборе амортизированной стоимости следует соблюдать осторожность. Если нужно провести анализ с использованием амортизированной стоимости, чтобы показать, что в наихудшем случае средняя стоимость операции невелика, полная амортизированная стоимость последовательности операций должна быть верхней границей полной фактической стоимости последовательности. Более того, как и в групповом анализе, это соотношение должно соблюдаться для всех последовательностей операций.
Если обозначить фактическую стоимость г-й операции через с;, а амортизированную стоимость г-й операции через с;, то это требование для всех последовательностей, состоящих из п операций, выразится следующим образом: (17.1) Общий кредит, хранящийся в структуре данных, представляет собой разность между полной амортизированной стоимостью и полной фактической стоимостью: Согласно неравенству (17.1), полный кредит, связанный со структурой данных, все время должен быть неотрицательным. Если бы полный кредит в каком-либо случае мог стать отрицательным (в результате недооценки ранних операций с надеждой восполнить счет впоследствии), то полная амортизированная стоимость в тот момент была бы ниже соответствующей фактической стоимости; значит, для последовательности операций полная амортизнрованная стоимость не была бы в этот момент времени верхней границей полной фактической стоимости. Таким образом, необходимо позаботиться, чтобы полный кредит для структуры данных никогда не был отрицательным.
Глава 17. Амортизационный анализ 489 Стековые операции Чтобы проиллюстрировать, как производится амортизационный анализ методом бухгалтерского учета, вернемся к примеру со стеком. Напомним, что фактическая стоимость операций была такой: Ризи 1, РОР 1, М1Л.Т1РОР ш1п(Й) а) где й — аргумент процедуры МиЬт1РОР, а а — размер стека на момент ее вызова. Присвоим приведенные ниже амортизированные стоимости: Р138Н 2, РОР О, М1л.т1РОР 0 . Заметим, что амортизированная стоимость операции Мыьт1РОР равна константе (0), в то время как ее фактическая стоимость — переменная величина.
В этой схеме все три амортизированные стоимости равны О (1), хотя в общем случае асимптотическое поведение амортизированных стоимостей рассматриваемых операций может быль разным. Теперь покажем, что любую последовательность стековых операций можно оплатить путем начисления амортизированных стоимостей. Предположим, что для представления каждой единицы затрат используется денежный счет. Пусть изначально стек пуст. Вспомним аналогию между стеком как структурой данных и стопкой тарелок в кафетерии, приведенную в разделе 10.1.
При добавлении тарелки в стопку 1 грн. затрачивается на оплату самой операции добавления, а е1це 1 грн. (из двух начисленных на операцию Рызн) остается в запасе, как бы на этой тарелке. В любой момент времени каждой тарелке стека соответствует 1 грн. кредита. Хранящаяся на тарелке 1 грн. предназначена для уплаты стоимости извлечения ее из стека. На операцию РОР ничего не начисляется, а ее фактическая стоимость выплачивается за счет кредита, который хранится в стеке. При извлечении тарелки изымается 1 грн.
кредита, которая используется для уплаты фактической стоимости операции. Таким образом, благодаря небольшой переоценке операции Розп, отпадает необходимость начислять какую-либо сумму на операцию РоР. Более того, на операцию Мгл.тп*оР также не нужно начислять никакой суммы. При извлечении первой тарелки мы берем из нее 1 грн.
кредита и тратим ее на оплату фактической стоимости операции РОР. При извлечении второй тарелки на ней также есть 1 грн. кредита на оплату фактической стоимости операции РОР и т.д. Таким образом, начисленной заранее суммы всегда достаточно для уплаты операций М1Л.тП'ОР. Другими словами, поскольку с каждой тарелкой стека Часть !Ч. Усовершенствованные методы разработки н анализа 490 связана 1 грн.
кредита и в стеке всегда содержится неотрицательное количество тарелок, можно быть уверенным, что сумма кредита всегда неотрицательна. Талии образом, для любой последовательности из и операций Рази, РОР и Мцьт!РОР полная амортнзированная стоимость является верхней границей полной фактичесюй стоимости. Поскольку полная амортизированная стоимость равна О (и), полная фактическая стоимость тоже определяется этим значением.
Приращение показаний бинарного счетчика В качестве другого примера, иллюстрирующего метод бухгалтерского учета, проанализируем операцию 1хскемейт, которая выполняется над бинарным изначально обнуленным счетчиком. Ранее мы убедились, что время выполнения этой операции пропорционально количеству битов, изменяющих свое значение. В данном примере это количество используется в качестве стоимости. Как и в предыдущем примере, для представления каждой единицы затрат (в данном случае — изменения битов) будет использован денежный счет. Чтобы провести амортизационный анализ, начислим на операцию, при которой биту присваивается значение 1 (т.е. бит устанавливается), амортизированную стоимость, равную 2 грн. Когда бит устанавливается, 1 грн.
(из двух начисленных) расходуется на оплату операции по самой установке. Оставшаяся 1 грн. вкладывается в этот бит в качестве кредита для последующего использования при его обнулении. В любой момент времени с каждой единицей содержащегося в счетчике значения связана 1 грн. кредита, поэтому для обнуления бита нет необходимости начислять какую-либо сумму; за сброс бита достаточно будет уплатить 1 грн. Теперь можно определить амортизированную стоимость операции 1нскемент. Стоимость обнуления битов в цикле за!е выплачивается за счет тех денег, юторые связаны с этими битами. В процедуре 1нскемент устанавливается не более одного бита (в строке б), поэтому амортизированная стоимость операции 1нсквмнчт не превышает 2 грн. Количество единиц в бинарном числе, представляющем показания счетчика, не может быть отрицательным, поэтому сумма кредита тоже всегда неотрицательна.
Таким образом, полная амортизированная стоимость и операций 1нскнмнчт равна О (и). Это и есть оценка полной фактичесюй стоимости. Упражнения 17.2-1. Над стеком выполняется последовательность операций; размер стека прн этом никогда не превышает й. После каждых к операций производится резервное копирование стека.
Присвоив различным стековым операциям соответствующие амортизированные стоимости, покажите, что стоимость и стеювых операций, включая копирование стека, равна О (и). Глава 17. Амортизационный анализ 491 17.2-2. Выполните упражнение 17.1-3, применив для анализа метод бухгалтерского учета. 17.2-3. Предположим, что нам нужно не только иметь возможность увеличивать показания счетчика, но и сбрасывать его (т.е. делать так, чтобы значения всех битов были равны О). Покажите, как осуществить реализацию счетчика в виде массива битов, чтобы для выполнения произвольной последовательности из и операций 1хскемеит и Кезет нал изначально обнуленном счетчиком потребовалось бы время О (и). (Указание: отслеживайте в счетчике самый старший разряд, содержащий единицу.) 17.3 Метод потенциалов Вместо представления предоплаченной работы в виде кредита, хранящегося в структуре данных вместе с отдельными объектами, при амортизированном анализе по методу иотецциалоа (рогепба! шег)зог1) такая работа представляется в вцле "потенциальной энергии", или просто "потенциала", который можно высвободить для оплаты последующих операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
