¿Por qué la inserción al final de una matriz dinámica O (1) mientras se inserta en el medio es O (n)?

Question

De acuerdo con el artículo de Wikipedia en matrices dinámicas , insertando / eliminando al final del la matriz es O (1), mientras que la inserción / eliminación desde el centro es O (n). ¿Por qué exactamente es eso?

También: si tengo una matriz dinámica con 5 elementos e inserto un nuevo elemento en la posición 6, la operación es O (n), mientras que si uso la función para agregar al final de la matriz, es O (1) . ¿No es esta la misma operación suponiendo que la matriz no necesita redimensionarse en ninguno de los casos? ¿O al agregar a la matriz dinámica realmente inserta el nuevo elemento en algún lugar además de la posición 6?

¡Gracias!

EDITAR: Creo que mi principal confusión es la diferencia entre insertar al final de la matriz e insertar en una posición específica que sea equivalente al final de la matriz.

Supongo que un puntero a la dirección de memoria del final de la matriz se mantiene a mano y es por eso que la operación de adición es rápida. Por el contrario, si especifico una posición precisa (incluso si es el final de la matriz) no sabrá que insertarse en esa posición equivale a usar la dirección de memoria mencionada anteriormente, por lo que tiene que atravesar toda la matriz, ¿eh?

Answer 1

El orden de magnitud dependería completamente de qué tipo de datos estructuran la " matriz dinámica " en realidad lo es ("matriz dinámica" no es una estructura de datos estrictamente definida, es más un resultado deseado que se logra al emplear una estructura de datos en particular). El ejemplo que proporcione sería el que se reflejaría mediante una matriz dinámica lograda al emplear una lista vinculada. Agregar al final podría ser O (1) si la estructura de la lista mantiene un puntero al elemento final. La inserción (independientemente del índice) requeriría atravesar la lista enlazada, lo que significa una operación por nodo hasta el índice deseado.

Answer 2

Para insertar al final de una matriz, simplemente debes colocar el elemento allí.

Para insertarlo en el medio de una matriz, necesitas mover los elementos después de ese punto hacia arriba en uno.

Para eliminar desde el final de una matriz, solo debes disminuir su cuenta en uno.

Para eliminar desde el medio, debes hacer que y desplacen los otros elementos hacia abajo.

Es el cambio que lo convierte en O (n).

Answer 3

Es bastante simple:

Insertar en el medio implica mover cada elemento posterior en 1. Para insertar al final, si hay espacio adicional reservado, el elemento se almacena allí, pero si no se asigna un nuevo espacio. Por lo tanto, esta operación se realiza en tiempo constante amortizado .

Answer 4

Agregando al excelente resumen de Adam Robinson: Esto no es solo una teoría. He visto varias situaciones en las que se construyó una matriz dinámica agregándola repetidamente al final de la matriz. Esto funciona para el rendimiento de (N ** 2) , ya que la matriz debe ser asignada repetidamente, lo que obliga a cada uno de sus miembros a copiarse en la nueva estructura de matriz. Las reasignaciones pueden ocurrir solo en 1/10 de las operaciones de anexos, pero eso es lo suficientemente malo, y aún es o (N ** 2) en cuanto al rendimiento.

En STL, esta penalización de rendimiento se puede evitar llamando a vector :: reserve (N) antes de escribir en el vector; pero ese paso a menudo se pasa por alto.

Answer 5

En realidad, no es Big-O pero Big-Theta .