Comprender y calcular el coste amortizado de las operaciones de rayos dinámicos
Los arrays dinámicos son estructuras de datos que se redimensionan automáticamente cuando alcanzan la capacidad. Comprender su coste amortizado ayuda a evaluar su eficiencia en múltiples operaciones.
¿Qué es el coste amortizado?
El coste amortizado es el coste medio por operación en una secuencia de operaciones. Suaviza los altos costos de redimensionamiento ocasional distribuyéndolos en muchas operaciones baratas.
Operaciones dinámicas de rayos de radiación
Las operaciones comunes en los arrays dinámicos incluyen la inserción, eliminación y redimensionamiento. La inserción al final es típicamente la operación más frecuente, que puede desencadenar el redimensionamiento cuando se supera la capacidad.
Calculando el coste amortizado
Al insertar elementos, el array se duplica cuando está lleno. El costo de redimensionamiento implica copiar todos los elementos existentes al nuevo array. Aunque el redimensionamiento es costoso, se produce infrecuentemente.
Por ejemplo, si un array comienza con la capacidad 1, la secuencia de costes de redimensionamiento sobre múltiples inserciones puede resumirse como:
- Insertar 1 elemento: costo 1
- Insertar 2o elemento: tamaño (costo 1), costo total 2
- Insertar el tercer elemento: tamaño (costo 2), costo total 3
- Insertar el cuarto elemento: tamaño (costo 4), costo total 4
El costo total sobre las inserciones n es proporcional a 2n, haciendo el costo amortizado por inserción aproximadamente O(1).