Qual é a complexidade assintótica das operações com a classe std::vector em C++?

Complexidade assintótica para as operações principais com std::vector:

Operação	Tempo médio	Tempo pior
Acesso ao elemento ([], at)	O(1)	O(1)
Inserção/remover no final	O(1)	O(N)
Inserção/remover no início/meio	O(N)	O(N)
Obter tamanho (size)	O(1)	O(1)
Alterar tamanho (resize)	O(N)	O(N)

Explicações:

• O(1) (tempo constante): A operação é realizada em um número fixo de passos, independentemente do tamanho do vetor.
• O(N) (tempo linear): O tempo de execução da operação é diretamente proporcional à quantidade de elementos no vetor (N).

Adicionalmente:

• Inserir/remover no final pode requerer O(N) no pior caso devido à reallocação de memória, quando a capacidade atual não é suficiente. Ao fazer realloc, um novo buffer maior é criado e todos os elementos existentes são copiados para ele. Graças à estratégia de alocação de memória (geralmente, duplicar a capacidade), o tempo médio de inserção/remoção no final é O(1).
• Inserir/remover no meio requer deslocar todos os elementos subsequentes, o que leva O(N) tempo.

Exemplo de realloc em push_back:

// Suponha que o vetor tem uma capacidade de 4 e está cheio
std::vector<int> vec = {1, 2, 3, 4}; // Capacidade = 4, Tamanho = 4

// Adicionar um novo elemento requer realloc
vec.push_back(5); // A capacidade pode passar a ser 8, e todos os elementos são copiados

// A operação push_back neste caso levou O(N) tempo,
// onde N é a quantidade de elementos antes da realloc.