Изменения
Нет описания правки
В качестве примера вновь рассмотрим стек с операцией <tex>\mathrm{multipop}{(a)}</tex>. Пусть потенциал {{---}} это количество элементов в стеке. Тогда:
## * <tex>a_{push} = 1 + 1 = 2,</tex> т. к. время выполнения операции <tex>\mathrm{push}{}</tex> {{---}} <tex>1</tex>, и изменение потенциала {{---}} тоже <tex>1</tex>.## * <tex>a_{pop} = 1 - 1 = 0,</tex> т. к. время выполнения операции <tex>\mathrm{pop}{}</tex> {{---}} <tex>1</tex>, а изменение потенциала {{---}} <tex>-1</tex>.## * <tex>a_{multipop} = k - k = 0,</tex> т. к. время выполнения операции <tex>\mathrm{multipop}{(k)}</tex> {{---}} <tex>k</tex>, а изменение потенциала {{---}} <tex>-k</tex>.
# Для любого <tex>i: \enskip \Phi_i = O(n),</tex> так как элементов в стеке не может быть больше <tex>n</tex>
#<tex>\mathrm{find}{}:</tex> Рассмотрим два случая:
#* Элементы распределяются по таблице достаточно равномерно: время поиска элемента в списке {{---}} <tex>O(1)</tex>, потенциал не изменяется, следовательно и реальная, и амортизированная сложности {{---}} <tex>1</tex>.
#* В случае, если все элементы оказываются размещены в одном списке, время поиска элемента достигает <tex>O(n)</tex>. Это время может быть улучшено до <tex>O(\log n)</tex>, если вместо списков использовать сбалансированные деревья поиска(в <tex>\mathrm{Java 8 }{}</tex> такая реализация <tex>\mathrm{HashSet }{}</tex> используется по стандарту для данных, которые можно сравнить).
#<tex>\mathrm{remove}{}: n</tex> уменьшается на единицу. Возможны три случая:
#*<tex dpi = "150">\genfrac{}{}{}{}{1}{2} \leqslant \alpha </tex>: потенциал уменьшается на 2, и амортизированное время <tex> 1 - 2 = -1 </tex>.
