Описание тега amortization
В информатике амортизированный анализ - это метод анализа алгоритмов, который учитывает всю последовательность операций программы.
Это позволяет установить границу наихудшего случая для производительности алгоритма независимо от входных данных, просмотрев все операции.
В основе метода лежит идея о том, что, хотя некоторые операции могут быть чрезвычайно затратными по ресурсам, они не могут выполняться с достаточно высокой частотой, чтобы утяжелить всю программу, потому что количество менее затратных операций намного превосходит количество дорогостоящих операций в программе. в долгосрочной перспективе, "окупив" программу за несколько итераций.
Это особенно полезно, потому что оно гарантирует производительность в худшем случае, а не делает предположения о состоянии программы.