3622
правки
Изменения
→Двоичный счётчик
=====Двоичный счётчик=====
Рассмотрим также двоичный инкрементальный счётчик (единственная возможная операция {{---}} увеличить значение на единицу).
Пусть результат увеличения счётчика {{---}} <tex>n</tex>, тогда в худшем случае необходимо изменить значения <tex> 1 + \lfloor \log n \rfloor</tex> бит, тогда и стоимость <tex>n</tex> операций {{---}} составит <tex> O(n \log n) </tex>.
Теперь воспользуемся для анализа методом усреднения.
Каждый следующий бит изменяет своё значение в <tex dpi = "150">n, \genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{4} \dots</tex> операциях.
<tex dpi = "150"> \sum\limits_{i=0}^{\lfloor \log n \rfloor} \genfrac{}{}{}{}{n}{2^i} < 2n = O(n)</tex>
В итоге амортизированная стоимость одной операции {{---}} <tex>O(1)</tex>.
