Амортизированный анализ: почему вставка в динамический массив — O(1) в среднем, если иногда O(n)?
std::vector::push_back иногда копирует весь массив при росте — это же O(n). Почему тогда везде пишут, что push_back амортизированно O(1)? Как это строго обосновать, а не «ну, редко же»?
2 ответа
Дело в стратегии удвоения: при заполнении вектор выделяет память вдвое больше и копирует туда старые элементы. Копирование стоит O(n), но происходит редко — после каждого удвоения нужно ещё столько же дешёвых вставок, прежде чем снова копировать.
Строгое обоснование (метод суммирования). Сделаем n вставок. Дорогие копирования случаются при размерах 1, 2, 4, 8, ..., до n. Суммарная стоимость всех копирований: 1 + 2 + 4 + ... + n < 2n. Плюс n дешёвых вставок по O(1). Итого общая работа O(n) на n вставок → в среднем O(1) на вставку. Это и есть амортизированная оценка: не «в среднем по вероятности», а «суммарно по worst-case последовательности, делённое на число операций».
Метод потенциалов (учётный метод): назначим каждой дешёвой вставке «цену» 3 единицы вместо 1. Одну тратим на саму вставку, две откладываем «в копилку». Когда массив заполнится и нужно скопировать k элементов, в копилке как раз накоплено достаточно, чтобы оплатить копирование. Амортизированная цена операции = 3 = O(1).
Важно: коэффициент роста должен быть константой > 1 (вдвое, в 1.5 раза). Если бы рост был «на +1 каждый раз», копирования происходили бы постоянно и n вставок стоили бы O(n^2). Именно геометрический рост даёт амортизированную константу. На олимпиаде это объясняет, почему vector без reserve обычно не виновник TLE.
Тот же амортизированный аргумент объясняет линейность стека/очереди на двух стеках, монотонной очереди, метода двух указателей: «дорого иногда = дёшево в среднем», потому что каждый элемент добавляется и удаляется ограниченное число раз. Практический совет для CP: если знаешь итоговый размер — делай v.reserve(n), тогда копирований при росте не будет вообще и пропадёт константа на реаллокациях. Это не меняет асимптотику, но иногда снимает borderline-TLE из-за константы.