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