Какая асимптотическая сложность вставки в vector?

Асимптотическая сложность вставки в std::vector

Ответ зависит от где вставляешь:

push_back(): O(1) amortized

Лучший случай: O(1) обычный

std::vector<int> v;
v.reserve(1000);  // Выделяем память заранее

for (int i = 0; i < 1000; ++i) {
    v.push_back(i);  // O(1) — просто копируем в конец
}

Худший случай: O(n) при переаллокации

std::vector<int> v;

for (int i = 0; i < 1000; ++i) {
    v.push_back(i);  // При заполнении capacity:
                      // 1. Выделяем новую память (обычно 2x)
                      // 2. Копируем все элементы (O(n))
                      // 3. Удаляем старую память
}

Почему O(1) amortized?

Средняя операция остаётся O(1), потому что переаллокация происходит редко:

• Вставляем элементы 1, 2, 3, ..., n
• Переаллокации на: 1, 2, 4, 8, 16, ... (степени 2)
• Суммарная работа: 1 + 2 + 4 + 8 + ... + n = 2n - 1 = O(n) для n вставок
• Среднее: O(n) / n = O(1) per insertion

// Пример: вставляем в вектор с reserve()
std::vector<int> v;
v.reserve(10000);  // Выделили много памяти

for (int i = 0; i < 10000; ++i) {
    v.push_back(i);  // Гарантированно O(1)!
    // Нет переаллокаций, только копирование одного элемента
}
// Итого: O(10000) = O(n)

insert(): O(n) в любой позиции

Вставка в середину:

std::vector<int> v = {1, 2, 3, 4, 5};
v.insert(v.begin() + 2, 99);  // Вставляем 99 на позицию 2

// Что происходит:
// [1, 2, 3, 4, 5]
// [1, 2, 99, 3, 4, 5] ← нужно сдвинуть элементы 3, 4, 5
// O(n) операция!

// Сложность вставки на разные позиции
std::vector<int> v;
for (int i = 0; i < 1000; ++i) v.push_back(i);

v.insert(v.begin(), 99);        // O(n) — сдвиг всех 1000 элементов
v.insert(v.begin() + 500, 99);  // O(n) — сдвиг 500 элементов
v.insert(v.end(), 99);          // O(1) — push_back в конец

Математика асимптотической сложности

Вставка n элементов по одному:

std::vector<int> v;

// Сценарий 1: insert в начало (очень плохо!)
for (int i = 0; i < n; ++i) {
    v.insert(v.begin(), i);  // O(1) + O(2) + O(3) + ... + O(n)
}                             // = O(n^2) total!

// Сценарий 2: push_back (хорошо)
for (int i = 0; i < n; ++i) {
    v.push_back(i);  // O(1) amortized
}                    // = O(n) total!

// Сценарий 3: insert в конец (хорошо)
for (int i = 0; i < n; ++i) {
    v.insert(v.end(), i);  // = push_back = O(1) amortized
}                          // = O(n) total!

Реальные примеры производительности

#include <vector>
#include <chrono>
#include <iostream>

int main() {
    const int N = 100000;
    
    // Тест 1: push_back (быстро)
    {
        auto start = std::chrono::high_resolution_clock::now();
        std::vector<int> v;
        for (int i = 0; i < N; ++i) {
            v.push_back(i);
        }
        auto end = std::chrono::high_resolution_clock::now();
        std::cout << "push_back: " 
                  << std::chrono::duration_cast<std::chrono::microseconds>
                     (end - start).count() << "µs" << std::endl;
        // ~500µs
    }
    
    // Тест 2: insert в начало (медленно!)
    {
        auto start = std::chrono::high_resolution_clock::now();
        std::vector<int> v;
        for (int i = 0; i < 10000; ++i) {
            v.insert(v.begin(), i);  // O(n^2)!
        }
        auto end = std::chrono::high_resolution_clock::now();
        std::cout << "insert begin: " 
                  << std::chrono::duration_cast<std::chrono::milliseconds>
                     (end - start).count() << "ms" << std::endl;
        // ~500ms для 10K элементов!
    }
    
    return 0;
}

Амортизированный анализ

Банковский метод:

• За каждый push_back платим не 1 условную единицу, а 3
• 1 единица идёт на копирование элемента
• 2 единицы откладываем на случай переаллокации

Когда происходит переаллокация:

• Новый размер: 2n (удвоение)
• Копируем n элементов, платим из отложенных
• Остаток откладываем для следующей переаллокации

Результат: среднее O(1) per insertion!

Оптимизация вставок

1. Используй reserve() для push_back:

std::vector<int> v;
v.reserve(100000);  // Выделяем всю память сразу

for (int i = 0; i < 100000; ++i) {
    v.push_back(i);  // Гарантированно O(1) без переаллокаций
}
// O(n) total, без дополнительных копий

2. Используй push_back вместо insert:

// Плохо: O(n^2)
std::vector<int> v;
for (int x : data) {
    v.insert(v.begin(), x);
}

// Хорошо: O(n)
std::vector<int> v;
for (int x : data) {
    v.push_back(x);  // Затем reverse если нужен обратный порядок
}
std::reverse(v.begin(), v.end());

3. Используй std::deque для вставок в начало:

// Если часто вставляешь в начало/конец
std::deque<int> d;  // O(1) для push_front и push_back
for (int x : data) {
    d.push_front(x);  // O(1) vs O(n) у vector
}

4. Используй std::list для вставок в середину:

// Если часто вставляешь в произвольные позиции
std::list<int> l;
for (auto it = l.begin(); it != l.end(); ++it) {
    l.insert(it, 99);  // O(1) vs O(n) у vector
}

Резюме

Главное: push_back в vector — один из самых быстрых способов заполнения контейнера. Используй его, а не insert!