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