Изменения
→Метод предоплаты (метод бухгалтерского учета)
Рассмотрим метод предоплаты на примере работы саморасширяющегося массива.
Пусть в массиве реализована операция <tex>add(x)</tex> - добавление элемента <tex>x</tex> в последнюю незанятую ячейку массива, если она есть. В противном случае эта операция выделяет память размером <tex>2n</tex>, если в массиве было <tex>n</tex> элементов, и добавляет <tex>x</tex> на <tex>n+1</tex> место в новом массиве.Покажем, что амортизированная стоимость операции <tex>add</tex> равна трем.<br>
==Литература==
Томас Кормен. Алгоритмы. Построение и анализ. - Санкт-Петербург, 2005. стр. 483-491.
