Изменения

Перейти к: навигация, поиск

Участник:Siziyman/Анализ

890 байт добавлено, 21:17, 10 мая 2014
Нет описания правки
Рассмотрим реализацию очереди на двух стеках. Пусть наши стеки имеют операции <tex>\mathrm{push}{}</tex> и <tex>\mathrm{pop}{}</tex>, обе стоимостью <tex>1</tex>.
Пусть каждое добавление элемента в очередь будет стоить 3 монеты. Это покроет , стоимость операций <tex>\mathrm{push}{}</tex> и <tex>\mathrm{pop}{}</tex> для переноса элемента из первого стека во второй, если потребуется, и ещё 1 монета будет нужна для того, чтобы поместить элемент в первый стек. Стоимость удаления элемента из очереди {{---}} 1 монета (она потребуется нам для удаления элемента из второго стека).
В лучшем случае(последовательность операций {{---}} добавить элемент и сразу же удалить его из очереди) мы тратим по монете непосредственно на <tex>\mathrm{push}{}</tex> в оба стека и <tex>\mathrm{pop}{}</tex> из первого стека, а стоимость удаления элемента из очереди непосредственно тратим на <tex>\mathrm{pop}{}</tex> из второго стека, и амортизированная сложность {{---}} <tex>O(1)</tex>. Рассмотрим другой случай. Предположим, мы имеем <tex>n</tex> операций добавления элемента в очередь и операцию удаления последнего добавленного в очередь элемента. Очевидно, это потребует <tex>O(n)</tex> времени в целом. Но известно, что каждый элемент был добавлен в стеки и удалён из них не более 1 раза, следовательно, амортизированная стоимость каждой операции в нашей последовательности {{---}} <tex>O(1)</tex>. Таким образом, амортизационная стоимость каждой операции для очереди {{---}} <tex> O(1) </tex>.
==Источники информации==
21
правка

Навигация