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