Рис. 18.1 Действие операции multipop на стеке S. (а) Начальное состояние стека. Multipop(5, 4) удаляет из стека верхние четыре элемента, и стек приходит в состояние (б). Если теперь применить операцию Multipop(5, 7), то стек станет пуст (в), так как перед применением этой операции в стеке было менее семи элементов.

содержится менее к элементов, то удаляется всё, что там есть). Её можно реализовать так (Stack-Empty возвращает true тогда и только тогда, когда стек пуст):

Пример работы операции Multipop приведен на рис. 18.1.

При применении операции Multipop(S, к) к стеку, содержащему s элементов, будет произведено mm(s,k) операций Pop. Поэтому (имеется в виду фактическая стоимость, а не учётная) время ее работы пропорционально min(s,A;).

Считая, что операции Push, Pop имеют единичную стоимость (имеется в виду фактическая стоимость, а не учётная), а операция Multipop имеет стоимость min(s,A;), оценим суммарную стоимость га операций, применённых к изначально пустому стеку. Стоимость любой из операций не превосходит га (самая дорогая операция Multipop стоит не более га, поскольку за га операций в стеке не наберётся более га элементов). Следовательно, суммарная стоимость га операций есть О (га2). Эта оценка, однако, слишком груба. Чтобы получить точную оценку, заметим, что, коль скоро первоначально стек был пуст, общее число реально выполняемых операций Pop (включая те из них, что вызываются из процедуры Multipop) не превосходит общего числа операций Push, а это последнее не превосходит га. Стало быть, стоимость любой последовательности из га операций Push, Pop и Multipop, примененных к пустому стеку, есть О (га). Тем самым можно объявить, что учётная стоимость каждой из операций есть 0(га)/га = 0(1).

Подчеркнём ещё раз, что наша оценка не является вероятностной: стоимость (в расчёте на одну операцию) оценивается для худшего случая.

Multipop (5, к)

counter value - значение счетчика, total cost - стоимость

Рис. 18.2 Состояния восьмибитового двоичного счетчика в процессе выполнения 16 последовательных операций INCREMENT. Заштрихованы биты, значения которых изменятся при следующей операции INCREMENT. В правой графе показана общая стоимость всех операций по установке или очистке битов, необходимых, чтобы досчитать до данного числа. Заметьте, что в строке номер к эта стоимость не превосходит 2к.

Двоичный счётчик

В этом разделе мы применим метод группировки к анализу к-битного двоичного счётчика. Счётчик реализован как массив битов А[0 . .к - 1] и хранит двоичную запись числа х = 2 i=o (так что А[0] - младший бит). Первоначально х = 0, т.е. A[i] = О для всех г. Определим операцию Increment (увеличить на 1 по модулю 2к) так:

Increment(A)

1г <- О

2while г < length[A] and A[i] = 1

3do А[г\ <- О

4i <r- i + 1

5if i < length[A]

6then A[i] <- 1

По существу тот же алгоритм используется в реальных компьютерах (каскадное сложение - см. раздел 29.2.1). На рис. 18.2 изображены состояния двоичного счетчика при 16 последовательных применениях операции Increment, начиная от 0 до 16. Увеличение счетчика на единицу происходит следующим образом: все начальные единичные биты в массиве А становятся нулями (цикл в строках 2-4), а следующий непосредственно за ними нулевой бит (если

таковой есть) устанавливается в единицу. Стоимость операции Increment линейно зависит от общего количества битов, подвергшихся очистке или установке. Отсюда сразу получается грубая оценка: поскольку в худшем случае (массив А состоит из одних единиц) меняются к битов, требуется О(пк) операций, чтобы сосчитать от 0 до га.

Чтобы получить более точную оценку, заметим, что не каждый раз значения всех к битов меняются. В самом деле, младший бит А[0] меняется при каждом исполнении операции Increment (см. рис. 18.2). Следующий по старшинству бит А[1] меняется только через раз: при отсчете от нуля до га этот бит меняется [п/2\ раз. Далее, A[N] меняется только каждый четвертый раз, и так далее: если 0 г lg га, то в процессе счета от 0 до га бит А[г] меняется [ra/28J раз, а если г > lgnJ> то бит г вообще не меняется. Стало быть, общее количество операций очистки и установки битов равно

Тем самым увеличение двоичного счётчика от 0 до га требует в худшем случае О (га) операций, причём константа не зависит от к (и равна 2); учётную стоимость каждой операции можно считать равной 0(п)/п = 0(1) (константа опять же не зависит от к).

Упражнения

18.1-1 Предположим, что мы разрешили не только операцию Multipop, но и Multipush, добавляющую к стеку произвольное количество элементов. Можно ли теперь считать учётную стоимость каждой операции равной 0(1)?

18.1-2 Определим для /г-битового двоичного счетчика операцию Decrement (вычитание единицы по модулю 2к). Покажите, последовательность из га операций Increment и Decrement в худшем случае требует времени @(пк).

18.1-3 Рассмотрим последовательность операций, в которой стоимость операции номер г равна г, если г является степенью двойки, и 1 в противном случае. Оцените среднюю стоимость одной операции в последовательности из га операций.

г=0

г=0

18.2. Метод предоплаты

При проведении амортизационного анализа по методу предоплаты (accounting method) каждой операции присваивается своя