Изменения
Нет описания правки
=====Двоичный счётчик=====
Рассмотрим также двоичный инкрементальный счётчик(единственная возможная операция - увеличить значение на единицу).
Пусть результат увеличения счётчика - <tex>n</tex>, тогда в худшем случае необходимо изменить значения <tex> 1 + \lfloor log n \rfloor</tex> бит, тогда стоимость <tex>n</tex> операций - <tex> O(n log n) </tex>.
Теперь воспользуемся для анализа методом усреднения.
=====Динамические хэш-таблицы=====
Рассмотрим хэш-таблицы, использующие цепочки для разрешения коллизий. Для того, чтобы поиск элемента в цепочке не начал слишком сильно влиять на производительность, введём величину <tex> \alpha </tex> {{---}} фактор загруженности(load factor) нашей таблицы.
Пусть в нашей таблице размером <tex> m </tex> хранится <tex> n </tex> элементов, тогда <tex dpi = "130"> \alpha = \genfrac{}{}{}{}{n}{m} </tex>
Введём значение <tex>\alpha_{max}</tex>, при превышении которого таблица будет пересоздана с увеличением размера и все элементы будут перераспределены по-новому(rehashing). Аналогично будем пересоздавать таблицу с уменьшением размера при удалении элемента.
Из-за этого сложность операции <tex>\mathrm{add}{}</tex> из <tex> O(1) </tex> станет в худшем случае <tex> O(n) </tex>, так как для пересоздания таблицы нам требуется <tex> O(n) </tex> операций.
Стоит отметить, что изменение размера массива всегда должно быть геометрическим(в <tex> k </tex> раз), потому как при изменении размера на константу нам потребуется <tex>O(n)</tex> раз пересоздать таблицу, что приведёт к сложности операции <tex>\mathrm{add}{}</tex> в <tex> O(n^2) </tex>.
Введём такую потенциальную функцию, что она будет "запасать" время по мере удаления фактора загруженности от <tex dpi = "130">\genfrac{}{}{}{}{1}{2}</tex>:
Рассмотрим реализацию очереди на двух стеках. Пусть наши стеки имеют операции <tex>\mathrm{push}{}</tex> и <tex>\mathrm{pop}{}</tex>, обе стоимостью <tex>1</tex>.
Пусть каждое добавление элемента в очередь будет стоить 3 монеты. Это покроет стоимость операций <tex>\mathrm{push}{}</tex> и <tex>\mathrm{pop}{}</tex> для переноса элемента из первого стека во второй, если потребуется, и ещё 1 монета будет нужна для того, чтобы поместить элемент в первый стек. Стоимость удаления элемента из очереди {{---}} 1 монета(она потребуется нам для удаления элемента из второго стека).
Таким образом, амортизационная стоимость каждой операции {{---}} <tex> O(1) </tex>.
