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

🔹 Почему удаление из конца у vector — это O(1)

✅ Вектор — это динамический массив:

• Вектор — это структура данных, в которой элементы хранятся в непрерывном участке памяти, как в обычном массиве.

• Он поддерживает быстрый доступ по индексу (O(1)) и эффективную вставку/удаление в конце.

✅ Как работает pop_back() или remove(size - 1):

• При вызове pop_back() в C++ или list.remove(list.size() - 1) в Java, происходит просто смещение логического размера массива на один элемент влево.

• Память не освобождается, просто объект на последней позиции:

  • деструктируется (в C++).

  • удаляется и становится недоступным (в Java).

✅ Никакого сдвига элементов не происходит:

• В отличие от удаления из начала или середины, здесь не нужно сдвигать остальные элементы.

• Поэтому время выполнения не зависит от количества элементов.

📘 Пример: C++

std::vector<int> v = {10, 20, 30, 40};
v.pop_back(); // Удаляет 40, сложность O(1)

• Элемент 40 уничтожается.

• Размер вектора уменьшается на 1.

• Внутренний буфер памяти не пересоздаётся.

📙 Пример: Java

ArrayList&lt;Integer&gt; list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);
list.remove(list.size() - 1); // Удаляет 30, сложность O(1)

• Объект на последнем индексе зануляется.

• Счётчик размера уменьшается.

• Не требуется перемещение других элементов.

🔍 Когда может быть не O(1)

Хотя теоретически и практически это O(1, амортизированная), на практике возможны тонкие детали:

📌 В C++

• Вызов pop_back() вызывает деструктор объекта.

• Если деструктор сложный (например, содержит удаление динамической памяти или вложенные вызовы) — операция может занять больше времени из-за внутренней логики, а не из-за vector.

📌 В Java

• ArrayList.remove(size - 1) также является O(1), но может вызвать GC (сборщик мусора), если объект становится недостижимым.

• Это не влияет на сложность, но может повлиять на задержки.

🧠 Что происходит внутри

В C++ (упрощённо):

template<typename T>
void vector<T>::pop_back() {
\--size_; // уменьшаем размер
data\[size_\].~T(); // вызываем деструктор
}

В Java:

public E remove(int index) {
E oldValue = elementData\[index\];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData\[--size\] = null;
return oldValue;
}

Если удаление из конца, numMoved == 0, и System.arraycopy() не вызывается.

📌 Сравнение со вставкой и удалением в других местах

🔄 Амортизированная вставка — но не амортизированное удаление

• При вставке в конец (push_back), может произойти перевыделение памяти, если ёмкость вектора закончилась (обычно x2).

• Это делает вставку амортизированной O(1).

• Удаление (pop_back) не требует перевыделения, поэтому является истинным O(1).

📉 Объём памяти не уменьшается автоматически

После pop_back:

• size уменьшается.

• capacity остаётся прежним.

• Чтобы реально уменьшить объём выделенной памяти, используют:

  • В C++: shrink_to_fit().

  • В Java: trimToSize().

Это не влияет на сложность удаления, но важно для управления памятью.

🧪 Итог с фокусом на анализ сложности

• Удаление последнего элемента из vector/ArrayList — это O(1).

• Это максимально эффективная операция, не требующая копирования или смещения элементов.

• Важно помнить: если удалять элементы в начале или середине, сложность станет линейной — O(n), так как остальные элементы нужно сдвинуть.

Поэтому при проектировании алгоритмов с векторами/списками важно по возможности ограничивать модификации концом коллекции.