Изменения
Нет описания правки
Определим <tex>t_1,t_2, ... t_n</tex> - время выполнения операций <tex>1,2, ... , n.</tex><br>
В методе средних амортизированная стоимость операций определяется следующим образом: суммарная стоимость всех операций алгоритма делится на их количество, т.е. <tex>\frac{\sum^{n}_{i=1} {t_i}}{n}</tex>. При этом каждой операции присвается одна и та же средняя амортизированная стоимость.
Рассмотрим стек с операцией <tex>multipop(a)</tex> - извлечение из стека <tex>a</tex> элементов. В худшем случае она работает за <tex>O(n)</tex> времени, если удаляются все элементы массива. Однако прежде чем удалить элемент, его нужно добавить в стек. Итак, если в стеке было не более <tex>n</tex> элементов, то в худшем случае с каждым из могли быть произведены 2 операции - добавление в стек и извлечение из него. Например, если было <tex>n</tex> операций <tex>push</tex> - добавление в стек, стоимость каждой <tex>O(1)</tex>, и одна операция <tex>multipop(n)</tex>, то суммарное время всех операций - <tex>O(2n)</tex>, всего операций <tex>n+1</tex>, а значит, амортизационная стоимость операции - <tex>O(1)</tex>.
==Метод предоплаты (метод бухгалтерского учета)==
