Изменения

Рассмотрим метод предоплаты на примере работы саморасширяющегося массива.<br>Пусть в массиве реализована операция реализованы операции <tex>addpush(x)</tex> - добавление элемента <tex>x</tex> в последнюю незанятую ячейку массива, если она есть. В противном случае эта , и операция <tex>add(x)</tex> - она выделяет память размером <tex>2n</tex>, если в массиве было <tex>n</tex> элементов, и добавляет <tex>x</tex> на <tex>n+1</tex> место в новом массиве. Покажем, что амортизированная стоимость операции <tex>add</tex> равна трем<tex>0(1)</tex>.<br>Представим, что использование определенного количества времени равносильно использованию определенного количества монет (плата за выполнение каждой операции). Перед использованием операции <tex>add(x)</tex> программе необходимо выполнить <tex>n</tex> операций <tex>push(x)</tex>. Пусть на каждую операцию <tex>push(x)</tex> тратися три монеты - одна на добавление элемента в массив, одну монету будем класть рядом с элементом на место <tex>i</tex>, и еще одну на <tex>i/2</tex> место в массиве (до первого выполнения операции <tex>add(x)</tex> эта монета никуда не кладется). К тому моменту, как нам нужно будет выполнить операцию <tex>add(x)</tex> около каждого элемента массива будет лежать по одной монете, которая и будет тратиться на его копирование во вновь созданный массив удвоенной длины. Таким образом, каждая операция <tex>push(x)</tex> стоит три монеты, а каждая операция <tex>add(x)</tex> ничего не стоит и произвродится за счет накопленных ранее монет, т.е. ее амортизированная стоимость равна <tex>O(1)</tex>, что и требовалось доказать.