120
правок
Изменения
Нет описания правки
Режим перекопирования активируется, когда в стеке <tex>L</tex> становится больше элементов, чем в стеке <tex>R</tex>. Пусть в стеке <tex>R</tex> в этот момент находилось <tex>n</tex> элементов, тогда в стеке <tex>L</tex> находилось <tex>n+1</tex> элементов. Заметим, что мы можем корректно обработать только <tex>n</tex> запросов <tex>pop</tex>, операции <tex>push</tex> и <tex>empty</tex> мы обрабатываем корректно всегда, следовательно мы должны закончить перекопирование за <tex>n+1</tex> операцию, включая активирующую.
Для заверешения завершения перекопирования нужно:
# Переместить все содержимое стека <tex>R</tex> в <tex>T</tex>, <tex>n</tex> операций.
# Переместить все содержимое стека <tex>L</tex> в <tex>R</tex>, <tex>n + 1</tex> операция.
Итого, мы должны сделать <tex>3 \cdot n + 3</tex> дополнительных действия за <tex>n + 1</tex> операций, то есть выполняя <tex>O(1)=3</tex> дополнительных действия на операцию, мы сможем завершить перекопирование и вернуться в обычный режим до исчерпания стека <tex>R'</tex>, получив <tex>O(1)</tex> реального времени и <tex>O(1)</tex> памяти на персистентность на операцию.
Теперь рассмотрим, какие изменения произошли за время перекопирования. Пусть среди <tex>n</tex> следующих за активацией операций у нас <tex>x</tex> операций <tex>pop</tex> и <tex>n-x</tex> операций <tex>push</tex>. Тогда в стеке <tex>R</tex> оказалось <tex>2 \cdot n + 1 - x</tex> элементов, а в новом стеке <tex>L</tex> оказалось <tex>n - x</tex> элементов. Тогда в стеке <tex>R</tex> на <tex>n+1</tex> больше элементов, чем в стеке <tex>L</tex>, а это значит, что до следующего режима перекопирования <tex>n + 2</tex> операции, и за это время мы успеем очистить старый стек <tex>Rc</tex>, в котором находится максимум <tex>n</tex> ненужных элементов, просто удаляя при каждой операции в обычном режиме один элемент из <tex>Rc</tex>, если он не пустой.
Заметим, что вышеприведенный алгоритм гарантирует нам, что в обычном режиме в стеке <tex>L</tex> находится не больше элементов, чем в <tex>R</tex>, так что проверка на пустоту очереди при обычном режиме сводится к проверке на пустоту стека <tex>R</tex>.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
