170
правок
Изменения
м
Нет описания правки
Математическое обоснование:
Пусть <tex>n</tex> {{---}} количество операций, <tex>m</tex> {{---}} размер стекаколичество элементов, задействованных в этих операциях. Очевидно <tex>m \leq n</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 {{---}} добавление и удаление. Тогда:
