Как определяется временная сложность операции вставки элемента в конец стандартного вектора в C++?

Временная сложность операции вставки элемента в конец стандартного вектора (std::vector) в C++ обычно амортизированная константная, то есть O(1) в среднем. Это связано с тем, что вектор выделяет память с запасом, и при добавлении элемента, если текущий буфер не заполнен, вставка происходит быстро — просто копируется или перемещается элемент.

Однако, когда внутренний буфер вектора заполнен, происходит перераспределение памяти: выделяется новый буфер большего размера (обычно в 2 раза больше), все элементы копируются или перемещаются в новый буфер, и старый освобождается. Эта операция занимает время O(n), где n — текущее количество элементов.

Но поскольку такие перераспределения происходят не при каждой вставке, а лишь периодически, амортизированная сложность вставки в конец остаётся O(1).

Пример:

std::vector<int> v;
for (int i = 0; i < 1000; ++i) {
    v.push_back(i); // амортизированно O(1)
}