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