Амортизированная сложность

Когда одна операция иногда дорогая

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

Амортизированный анализ распределяет редкие дорогие действия по множеству дешёвых. Он отвечает на вопрос: сколько в среднем приходится платить за одну операцию, если выполнить их много подряд?

Пример с расширяемым массивом

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

if (size == elements.length) {
    elements = Arrays.copyOf(elements, elements.length * 2);
}

elements[size++] = value;

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

Почему получается O(1) амортизированно

Если ёмкость растёт вдвое, расширения происходят примерно при размерах 1, 2, 4, 8, 16 и так далее. За последовательность из n добавлений суммарное количество скопированных элементов остаётся порядка n. Если распределить эту работу на все n операций, получается постоянная амортизированная стоимость добавления — O(1).

Это не означает, что каждое добавление выполняется за O(1). Конкретная операция расширения может стоить O(n), но такие операции достаточно редкие, чтобы длинная последовательность добавлений в целом оставалась линейной.