Aquí hay un desglose:
* insertando al final (usando `push_back` o equivalente): Esto es generalmente o (1) - tiempo constante amortizado . "Amortizado" significa que, si bien ocasionalmente el vector necesita reasignar su memoria subyacente (que toma O (n) tiempo), la mayoría de las veces la inserción simplemente coloca el elemento en la siguiente ranura disponible. Sobre muchas inserciones, el tiempo promedio es casi constante.
* Insertar en una posición específica (usando `Insertar (posición de iterador, valor)` o equivalente): Este es o (n) - tiempo lineal . He aquí por qué:
1. Encontrar la posición: Si el iterador se proporciona directamente, encontrar la posición dentro del vector existente suele ser O (1). Sin embargo, si tiene que * buscar * el punto de inserción (por ejemplo, insertar en un orden ordenado), el tiempo de búsqueda en sí podría ser o (n) u o (log n) dependiendo del algoritmo de búsqueda utilizado (búsqueda lineal o búsqueda binaria, respectivamente). Pero la parte cambiante domina.
2. Elementos de cambio: Para dejar espacio para el nuevo elemento, todos los elementos * después de * el punto de inserción debe desplazarse una posición a la derecha. En el peor de los casos (insertando al principio), debe cambiar los elementos `n`. En el caso promedio (insertando en el medio), cambia aproximadamente los elementos `n/2`. En cualquier caso, la operación de cambio aporta o (n) complejidad del tiempo.
Tabla de resumen:
| Ubicación de inserción | Complejidad del tiempo | Explicación |
| ---------------------- | ---------------
| End (push_back) | O (1) (amortizado) | Por lo general, tiempo constante. En ocasiones, se puede necesitar una reasignación, pero en muchas inserciones, el tiempo promedio permanece cerca de constante. |
| Posición específica | O (n) | Requiere cambiar todos los elementos después del punto de inserción. La operación de cambio domina la complejidad del tiempo. Nota:Si el punto de inserción debe encontrarse buscando dentro del vector, ese tiempo de búsqueda se agregaría a la complejidad total. |
Consideraciones importantes:
* Reallocación: Cuando un vector se queda sin capacidad, necesita reasignar un bloque de memoria más grande y copiar todos los elementos existentes en el nuevo bloque. Esta operación de reasignación es o (n). Sin embargo, los vectores a menudo duplican su capacidad cada vez que se reasignan, lo que hace que la reasignación sea lo suficientemente poco frecuente como para que el costo se amortice por muchas inserciones.
* Implementación vectorial: Los detalles de las implementaciones de vectores pueden afectar ligeramente el rendimiento. Por ejemplo, algunas implementaciones pueden usar técnicas de gestión de memoria más sofisticadas.
Ejemplo (C ++):
`` `CPP
#Include
#Include
int main () {
std ::vector
// insertando al final (amortizado o (1))
myVector.push_back (6);
std ::cout <<"después de push_back:";
para (int x:myVector) std ::cout <
// insertar en una posición específica (o (n))
myVector.insert (myVector.begin () + 2, 10); // insertar 10 en el índice 2
std ::cout <<"después de insertar:";
para (int x:myVector) std ::cout <
regresar 0;
}
`` `` ``
En resumen, tenga en cuenta * donde * estás insertando en un vector. `push_back` es tu amigo si solo necesitas agregar al final. Si necesita insertar en el medio, considere las implicaciones de rendimiento, especialmente si está haciendo muchas de esas inserciones. Si se requieren inserciones medias frecuentes, las estructuras de datos alternativas como listas vinculadas o árboles equilibrados pueden ser más adecuadas.