170
правок
Изменения
Нет описания правки
====Пример====
Рассмотрим стек с операцией <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>.
Математическое обоснование:
Пусть <tex>n</tex> {{---}} количество операций, <tex>m</tex> {{---}} размер стека. Тогда:
2) Для любого <tex>i: \enskip \phi_i = O(n \relax f(n, m))</tex>
|proof =
<tex dpi = "150">a = \frac{\sum\limits^{n}_{i = 1} {t_i}}{n} = \frac{\sum\limits^{n}_{i = 1} {a_i} + \sum\limits^{n - 1}_{i = 0} {\phi_i} - \sum\limits^{n}_{i = 1} {\phi_i} }{n} = \frac{n \relax O(f(n, m)) * n + \phi_0 - \phi_n}{n} = O(f(n, m))</tex>
}}
====Пример====
В качестве примера вновь рассмотрим стек с операцией <tex>multipop(a)</tex>. Пусть потенциал {{---}} это количество элементов в стеке. Тогда:
1.1) <tex>a_{push} = 1 + 1 = 2,</tex> т. к. время выполнения операции push {{---}} 1, и изменение потенциала {{---}} тоже 1.
1.2) <tex>a_{pop} = 1 - 1 = 0,</tex> т. к. время выполнения операции pop {{---}} 1, а изменение потенциала {{---}} -1.
1.3) <tex>a_{multipop} = k + k = 0,</tex> т. к. время выполнения операции multipop(k) {{---}} k, а изменение потенциала {{---}} -k.
2) Для любого <tex>i: \enskip \phi_i = O(n),</tex> так как элементов в стеке не может быть больше <tex>n</tex>
Таким образом, <tex>f(n, m) = 1</tex>, а значит, cредняя амортизационная стоимость операций <tex>a = O(1)</tex>.
==Метод предоплаты==
