3622
правки
Изменения
→Стек с multipop
Пусть <tex>n</tex> {{---}} количество операций, <tex>m</tex> {{---}} количество элементов, задействованных в этих операциях. Очевидно, <tex>m \leqslant n</tex> Тогда:
<tex dpi = "150">a = \genfrac{}{}{}{}{\sum\limits^{n}_{i=1} {t_i}}{n} = \genfrac{}{}{}{}{\sum\limits^{n}_{i=1} \sum\limits^{m}_{j=1} {t_{ij}}}{n} = \genfrac{}{}{}{}{\sum\limits^{m}_{j=1} \sum\limits^{n}_{i=1} {t_{ij}}}{n},</tex> где <tex>{t_{ij}}</tex> {{---}} стоимость <tex>i</tex>-ой операции над <tex>j</tex>-ым элементом. Величина <tex>\sum\limits^{n}_{i=1} {t_{ij}}</tex> не превосходит <tex>2</tex>, т. к. так как над элементом можно совершить только две операции, стоимость которых равна <tex>1</tex> {{---}} добавление и удаление. Тогда:
<tex dpi = "150">a \leqslant \genfrac{}{}{}{}{2m}{n} \leqslant 2,</tex> так как <tex>m \leqslant n</tex>.
