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