A complexidade do tempo da operação `inser 'em um vetor depende de onde Você está inserindo o elemento.

Aqui está um colapso:

* inserindo no final (usando `push_back` ou equivalente): Isso geralmente é o (1) - tempo constante amortizado . "Amortizado" significa que, embora ocasionalmente o vetor precise realocar sua memória subjacente (que leva o tempo O (n)), na maioria das vezes a inserção está simplesmente colocando o elemento no próximo slot disponível. Durante muitas inserções, o tempo médio está próximo da constante.

* Inserção em uma posição específica (usando `insert (posição do iterador, valor)` ou equivalente): Este é o (n) - tempo linear . Aqui está o porquê:

1. Encontrando a posição: Se o iterador for fornecido diretamente, encontrar a posição dentro do vetor existente é geralmente O (1). No entanto, se você precisar * pesquisar * o ponto de inserção (por exemplo, inserir em uma ordem classificada), o próprio tempo de pesquisa pode ser O (n) ou O (log n), dependendo do algoritmo de pesquisa usado (pesquisa linear ou pesquisa binária, respectivamente). Mas a parte muda domina.

2. Elementos de mudança: Para abrir espaço para o novo elemento, todos os elementos * Após * o ponto de inserção deve ser deslocado uma posição para a direita. Na pior das hipóteses (inserindo no início), você deve mudar os elementos `n`. No caso médio (inserindo no meio), você muda aproximadamente `n/2` elementos. Em ambos os casos, a operação de mudança contribui o (n) complexidade do tempo.

Tabela de resumo:

| Localização de inserção | Complexidade do tempo | Explicação |
| ------------------------ | ------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------
| Fim (push_back) | O (1) (amortizado) | Geralmente tempo constante. Ocasionalmente, a realocação pode ser necessária, mas, durante muitas inserções, o tempo médio permanece próximo da constante. |
| Posição específica | O (n) | Requer mudança de todos os elementos após o ponto de inserção. A operação de mudança domina a complexidade do tempo. Nota:Se o ponto de inserção precisar ser encontrado pesquisando dentro do vetor, esse tempo de pesquisa será adicionado à complexidade total. |

Considerações importantes:

* realocação: Quando um vetor fica sem capacidade, ele precisa realocar um bloco maior de memória e copiar todos os elementos existentes no novo bloco. Esta operação de realocação é O (n). No entanto, os vetores geralmente dobram sua capacidade cada vez que realocam, tornando a realocação pouco frequente o suficiente para que o custo seja amortizado por muitas inserções.

* Implementação do vetor: As especificidades das implementações vetoriais podem afetar ligeiramente o desempenho. Por exemplo, algumas implementações podem usar técnicas de gerenciamento de memória mais sofisticadas.

Exemplo (C ++):

`` `cpp
#include
#include

int main () {
std ::vector myVector ={1, 2, 3, 4, 5};

// inserindo no final (amortizado o (1))
myvector.push_back (6);
std ::cout <<"após push_back:";
para (int x:myvector) std ::cout < std ::cout <
// inserindo em uma posição específica (o (n))
myvector.insert (myvector.begin () + 2, 10); // Inserir 10 no índice 2
std ::cout <<"Após a inserção:";
para (int x:myvector) std ::cout < std ::cout <
retornar 0;
}
`` `

Em resumo, lembre -se de * onde * você está inserindo em um vetor. `push_back` é seu amigo se você precisar adicionar ao final. Se você precisar inserir no meio, considere as implicações de desempenho, especialmente se você estiver fazendo muitas dessas inserções. Se forem necessárias inserções médias frequentes, estruturas de dados alternativas, como listas vinculadas ou árvores equilibradas, podem ser mais adequadas.