Асимптотическая сложность для основных операций с std::vector:
| Операция | Среднее время | Худшее время |
|---|
Доступ к элементу ([], at) | O(1) | O(1) |
| Вставка/удаление в конце | O(1) | O(N) |
| Вставка/удаление в начале/середине | O(N) | O(N) |
Получение размера (size) | O(1) | O(1) |
Изменение размера (resize) | O(N) | O(N) |
Пояснения:
- O(1) (константное время): Операция выполняется зафиксированное количество шагов, независимо от размера вектора.
- O(N) (линейное время): Время выполнения операции прямо пропорционально количеству элементов в векторе (N).
Дополнительно:
- Вставка/удаление в конце может потребовать O(N) в худшем случае из-за перераспределения памяти (реаллокации), когда текущий объем памяти оказывается недостаточным. При реаллокации создается новый, больший буфер, и все существующие элементы копируются в него. За счет стратегии выделения памяти (как правило, удвоение емкости), среднее время вставки/удаления в конце оказывается O(1).
- Вставка/удаление в середине требует смещения всех последующих элементов, что занимает O(N) времени.
Пример реаллокации при push_back:
cpp