Изменения

Представим, что использование определенного количества времени равносильно использованию определенного количества монет (плата за выполнение каждой операции). В методе предоплаты каждому типу операций присваивается своя учётная стоимость. Эта стоимость может быть больше фактической, в таком случае лишние монеты используются как резерв для выполнения других операций в будущем, а может быть меньше, тогда гарантируется, что текущего накопленного резерва достаточно для выполнения операции. Если получится Для доказательства оценки средней амортизационной стоимости <tex>O(f(n, m))</tex> нужно построить учётные стоимости так, что для каждой операции она будет составлять <tex>O(f(n, m))</tex>. Тогда для последовательности из <tex>n</tex> операций суммарно будет затрачено <tex>n \cdot O(f(n, m))</tex> монет, следовательно, то и cредняя амортизационная стоимость операций будет <tex dpi = "150">a = \frac{\sum\limits^{n}_{i = 1} {t_i}}{n} = \frac{n \cdot O(f(n, m))}{n}</tex> <tex>= O(f(n, m))</tex>.