Назад к вопросам
Junior
77
questionbank
Какова асимптотическая сложность операций с классом std::vector в C++?
Sobes Copilot
Получайте ответы в реальном времени
Ответ от нейросети
sobes.tech AI
Асимптотическая сложность для основных операций с 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:
// Допустим, вектор имеет емкость 4 и заполнен
std::vector<int> vec = {1, 2, 3, 4}; // Емкость = 4, Размер = 4
// Добавление нового элемента требует реаллокации
vec.push_back(5); // Возможно, емкость стала 8, все элементы скопированы
// Операция push_back в этом случае заняла O(N) время,
// где N - количество элементов до реаллокации.