3622
правки
Изменения
→Очередь на двух стеках
Пусть каждое добавление элемента в очередь будет стоить <tex>3</tex> монеты, стоимость удаления элемента из очереди {{---}} <tex>1</tex> монета.
В лучшем случае(последовательность операций {{---}} добавить элемент и сразу же удалить его из очереди) мы тратим по монете непосредственно на <tex>\mathrm{push}{}</tex> в оба стека и <tex>\mathrm{pop}{}</tex> из первого стека, а стоимость удаления элемента из очереди непосредственно тратим на <tex>\mathrm{pop}{}</tex> из второго стека, и амортизированная сложность {{---}} <tex>O(1)</tex>.
Рассмотрим другой случай. Предположим, мы имеем <tex>n</tex> операций добавления элемента в очередь и операцию удаления последнего добавленного в очередь элемента. Очевидно, это потребует <tex>O(n)</tex> времени в целом. Но известно, что каждый элемент был добавлен в стеки и удалён из них не более <tex>1</tex> раза, следовательно, амортизированная стоимость каждой операции в нашей последовательности {{---}} <tex>O(1)</tex>.
Таким образом, амортизационная стоимость каждой операции для очереди {{---}} <tex> O(1) </tex>.
== См. также ==
*[[Хеш-таблица]]
