Структуры данных и модели вычислений
Амортизационный анализ
Наряду с получением верхних и нижних оценок и оценок в среднем, часто используются так называемые амортизационные оценки.
Амортизационный анализ применяется при оценке времени выполнения корректной последовательности, состоящей из однотипных или разнотипных операций с некоторой структурой данных. Если верхнюю оценку времени выполнения одной операции умножить на , получим верхнюю оценку выполнения всех операций. Часто такая оценка бывает сильно завышенной. Иногда длительное время выполнения очередной операции влечет за собой малое время выполнения следующих операций. Более того, такая ситуация может создаваться искусственно, то есть при выполнении очередной операции мы можем готовить почву для более эффективного выполнения следующей. Поэтому возникает задача изучения асимптотического поведения гарантированной оценки для среднего времени выполнения одной операции.
При амортизационном анализе определяется некоторая так называемая учетная (амортизационная) стоимость одной операции, которая может быть как больше, так и меньше реальной стоимости конкретной операции. Но при этом для любой корректной последовательности операций фактическая суммарная длительность всех операций не должна превосходить суммы их учетных стоимостей. Зная учетную стоимость одной операции, верхнюю оценку времени выполнения последовательности из операций можно получить, умножив ее на .
Ниже рассмотрим три часто используемых метода амортизационного анализа: метод группировки, метод предоплаты и метод потенциалов.
Метод группировки. Предположим, что мы оценили сверху время выполнения последовательности из операций, установив, что она не превосходит , тогда величину
объявим учетной стоимостью любой операции из рассматриваемой последовательности, независимо от ее длительности.
Метод предоплаты. В этом методе операции разных типов получают разные учетные стоимости, причем эти стоимости могут быть как больше, так и меньше фактических. Если учетная стоимость превосходит фактическую, то разность между ними рассматривается как резерв на оплату в будущем тех операций, у которых учетная стоимость ниже реальной.
