Описание тега amortized-analysis

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

Иногда это стремление к сокращению общего времени вычислений требует алгоритмов, которые могут иметь высокую сложность наихудшего случая для одного экземпляра, но в среднем будут иметь хорошую временную сложность.

Хорошо известный пример этого - как лучше увеличить объем памяти в std::vector<> после push_back который превышает выделенную в данный момент память, т. е. путем перераспределения массива, который M раз больше, где Mможет быть около 1,5. Амортизированное время работы для этого постоянно (O(1)) так долго как M>1. Наивно перераспределяя фиксированный объем памяти для каждого такогоpush_back среднее время O(N), где N это количество push_backс.

Вот лекция MIT Open Courseware, в которой они касаются амортизированного анализа.