Изменения

1.1) ## <tex>a_{push} = 1 + 1 = 2,</tex> т. к. время выполнения операции <tex>\mathrm{push}{}</tex> {{---}} 1, и изменение потенциала {{---}} тоже 1. 1.2) ## <tex>a_{pop} = 1 - 1 = 0,</tex> т. к. время выполнения операции <tex>\mathrm{pop}{}</tex> {{---}} 1, а изменение потенциала {{---}} -1. 1.3) ## <tex>a_{multipop} = k - k = 0,</tex> т. к. время выполнения операции <tex>\mathrm{multipop}{(k)}</tex> {{---}} k, а изменение потенциала {{---}} -k. 2) # Для любого <tex>i: \enskip \Phi_i = O(n),</tex> так как элементов в стеке не может быть больше <tex>n</tex>

#Операция <tex>\mathrm{add}{}: n</tex> увеличивается на единицу. Следовательно, имеются три случая: ##<tex dpi = "130">\genfrac{}{}{}{}{1}{2} \leqslant \alpha < 1 </tex>: потенциал увеличивается на 2, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>. ##<tex dpi = "130">\alpha < \genfrac{}{}{}{}{1}{2}</tex>: потенциал уменьшается на 2, и амортизированное время <tex> 1 - 2 = -1 </tex>. ##<tex>\alpha = 1</tex>: Таблица увеличивается в размере, так что реальная сложность {{---}} <tex> 1 + m </tex>. Но потенциал изменяется с <tex>m</tex> до нуля, следовательно амортизационная сложность {{---}} <tex> 1 + m - m = 1</tex>. #<tex>\mathrm{find}{}:</tex> Потенциал не изменяется, следовательно и реальная, и амортизированная сложности {{---}} <tex>1</tex>. #<tex>\mathrm{remove}{}: n</tex> уменьшается на единицу. Возможны три случая: ##<tex dpi = "130">\genfrac{}{}{}{}{1}{2} \leqslant \alpha < 1 </tex>: потенциал уменьшается на 2, и амортизированное время <tex> 1 - 2 = -1 </tex>. ##<tex dpi = "130">\alpha < \genfrac{}{}{}{}{1}{2}</tex>: потенциал увеличивается на 2, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>. ##<tex>\alpha = 1</tex>: Таблица уменьшается в размере, следовательно реальная сложность {{---}} <tex dpi = "130"> 1 + \genfrac{}{}{}{}{m}{4}</tex>, а потенциал меняется от <tex dpi = "130">\genfrac{}{}{}{}{m}{2}</tex> до нуля, следовательно амортизированная стоимость {{---}} <tex dpi = "130"> 1 + \genfrac{}{}{}{}{m}{4} - \genfrac{}{}{}{}{m}{2} = 1 - \genfrac{}{}{}{}{m}{4}</tex>.