N-разрядный счетчик амортизированного анализа
Предположим, у нас есть двоичный счетчик, который поддерживает две операции: увеличение и сброс всех битов до нуля. Если модификация или проверка одного бита занимает время тета (1), как счетчик может быть реализован как массив битов, чтобы любая последовательность операций приращения и сброса на первоначально нулевом счетчике занимала O(n) времени?
Посредством совокупного анализа и того факта, что не все биты должны каждый раз переворачиваться, я смог увидеть, что счетчик, который просто позволяет увеличивать, занимает время O(n) для n операций. Но я застрял на том, как реализовать счетчик сброса приращения. Насколько я могу судить, сальто - это сальто, и ничто волшебным образом не заставит 1111 стать 0000 быстрее, чем обычно. Однако я замечаю, что с операцией инкремента мы не будем слишком часто сталкиваться с очень дорогой ситуацией "все 1".
Я предполагаю, что реальный вопрос заключается в том, существует ли на самом деле стратегия реализации эффективного счетчика с помощью утилиты сброса, или я просто пытаюсь доказать, что он получился бы как счетчик только с операцией приращения? Единственный совет, который я имею, - "держать указатель на старшем 1", что, по-видимому, предполагает первое.