Структуры данных и модели вычислений
Амортизационный анализ работы двоичного счетчика
Рассмотрим работу -разрядного двоичного сбрасываемого счетчика, реализованного как массив битов , хранящий двоичную запись числа . Будем считать, что — младший разряд. Пусть первоначально . Единственной операцией в нашем примере будет операция Increment, увеличивающая на 1 по модулю .
Увеличение счетчика на единицу происходит следующим образом: все начальные единичные биты в массиве , если они есть, становятся нулями, а следующий непосредственно за ними нулевой бит, если он есть, устанавливается в единицу. Стоимость операции Increment линейно зависит от общего количества битов, подвергшихся изменению. Каждое такое изменение будем считать элементарной операцией.
Анализ работы двоичного счетчика методом группировки. Применим метод группировки для анализа сложности -кратного выполнения операции Increment. Поскольку в худшем случае, когда массив состоит из одних единиц, меняются все
битов, то -кратное выполнение операции Increment может быть оценено как элементарных операций. Но эта оценка слишком груба.
Чтобы получить более точную оценку, учтем, что не каждый раз значения всех битов меняются. В самом деле, младший бит меняется при каждом исполнении операции Increment. Следующий по старшинству бит меняется только через раз. При счете от нуля до этот бит меняется раз. Бит меняется только каждый четвертый раз, и так далее. Заметим, что если , то в процессе счета от до
разряд меняется раз, а если , то он вообще не меняется. Следовательно, общее количество операций зануления и записи 1 равно
Тем самым, увеличение двоичного счетчика от до
требует не более операций, причем константа не зависит от и равна . Учетную стоимость операции Increment можно считать равной .
Анализ работы двоичного счетчика методом предоплаты. Применим метод предоплаты для анализа сложности -кратного выполнения операции Increment. Будем считать, что реальная стоимость изменения бита составляет рубль. Установим такие учетные стоимости: рубля за запись единицы, за очистку. При каждой установке бита в единицу одним из двух рублей учетной стоимости будем расплачиваться за реальные затраты на эту установку, а второй рубль, остающийся в резерве, будем "прикреплять" к рассматриваемому биту.
