170
правок
Изменения
м
Нет описания правки
Пусть <tex>n</tex> {{---}} количество операций, <tex>m</tex> {{---}} размер стека. Тогда:
<tex dpi = "150">a = \frac{\sum\limits^{n}_{i=1} {t_i}}{n} = \frac{\sum\limits^{n}_{i=1} \sum\limits^{m}_{j=1} {t_{ij}}}{n} = \frac{\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> не превосходит 2, т. к. над элементом можно совершить только 2 операции, время выполнения стоимость которых равно равна 1 {{---}} добавление и удаление. Тогда:
<tex>a \leq \frac{2m}{n} \leq 2,</tex> так как <tex>m \leq n</tex>.
