Matriz dinámica
En la informática , una matriz dinámica , array growable , matriz de tamaño variable , tabla dinámica , array mutable , o lista de arreglo es un acceso aleatorio , la lista de tamaño variable de estructura de datos que permite a los que se añaden o se quitan elementos. Se suministra con bibliotecas estándar en muchos lenguajes de programación convencionales modernos. Las matrices dinámicas superan un límite de matrices estáticas , que tienen una capacidad fija que debe especificarse en la asignación.
Una matriz dinámica no es lo mismo que una matriz asignada dinámicamente , que es una matriz cuyo tamaño es fijo cuando se asigna la matriz, aunque una matriz dinámica puede usar una matriz de tamaño fijo como back-end. [1]
Se puede construir una matriz dinámica simple asignando una matriz de tamaño fijo, generalmente más grande que el número de elementos requeridos inmediatamente. Los elementos de la matriz dinámica se almacenan de forma contigua al comienzo de la matriz subyacente, y las posiciones restantes hacia el final de la matriz subyacente están reservadas o no se utilizan. Se pueden agregar elementos al final de una matriz dinámica en tiempo constanteutilizando el espacio reservado, hasta que este espacio se consuma por completo. Cuando se consume todo el espacio y se debe agregar un elemento adicional, es necesario aumentar el tamaño de la matriz de tamaño fijo subyacente. Normalmente, el cambio de tamaño es caro porque implica asignar una nueva matriz subyacente y copiar cada elemento de la matriz original. Los elementos se pueden eliminar del final de una matriz dinámica en tiempo constante, ya que no es necesario cambiar el tamaño. El número de elementos utilizados por el contenido de la matriz dinámica es su tamaño o tamaño lógico , mientras que el tamaño de la matriz subyacente se denomina capacidad o tamaño físico de la matriz dinámica , que es el tamaño máximo posible sin reubicar datos. [2]
Una matriz de tamaño fijo será suficiente en aplicaciones donde el tamaño lógico máximo es fijo (por ejemplo, por especificación), o puede calcularse antes de que se asigne la matriz. Podría preferirse una matriz dinámica si:
Para evitar incurrir en el costo de cambiar el tamaño muchas veces, los arreglos dinámicos cambian de tamaño en una gran cantidad, como duplicar su tamaño, y usan el espacio reservado para futuras expansiones. La operación de agregar un elemento al final podría funcionar de la siguiente manera:
A medida que se insertan n elementos, las capacidades forman una progresión geométrica . Expandir la matriz en cualquier proporción constante a asegura que insertar n elementos toma O ( n ) tiempo en general, lo que significa que cada inserción toma un tiempo constante amortizado . Muchos arreglos dinámicos también desasignan parte del almacenamiento subyacente si su tamaño cae por debajo de un cierto umbral, como el 30% de la capacidad. Este umbral debe ser estrictamente menor que 1 / a para proporcionar histéresis (proporciona una banda estable para evitar el crecimiento y la contracción repetidos) y admite secuencias mixtas de inserciones y extracciones con un costo constante amortizado.
