Dinamización

Proceso de transformación de una estructura de datos estática en una dinámica

En informática , la dinamización es el proceso de transformar una estructura de datos estática en una dinámica. Aunque las estructuras de datos estáticas pueden proporcionar una funcionalidad muy buena y consultas rápidas, su utilidad es limitada debido a su incapacidad de crecer o contraerse rápidamente, lo que las hace inaplicables para la solución de problemas dinámicos , donde los datos de entrada cambian. Las técnicas de dinamización proporcionan formas uniformes de crear estructuras de datos dinámicas.

Problemas de búsqueda descomponibles

Definimos el problema de búsqueda de la coincidencia de predicado en el conjunto como . El problema es descomponible si el conjunto se puede descomponer en subconjuntos y existe una operación de unificación de resultados tal que . ${\displaystyle P}$ ${\displaystyle M}$ ${\displaystyle S}$ ${\displaystyle P(M,S)}$ ${\displaystyle P}$ ${\displaystyle S}$ ${\displaystyle S_{i}}$ ${\displaystyle +}$ ${\displaystyle P(M,S)=P(M,S_{0})+P(M,S_{1})+\dots +P(M,S_{n})}$

Descomposición

La descomposición es un término que se utiliza en informática para dividir estructuras de datos estáticos en unidades más pequeñas de tamaño desigual. El principio básico es la idea de que cualquier número decimal se puede traducir a una representación en cualquier otra base. Para obtener más detalles sobre el tema, consulte Descomposición (informática) . Para simplificar, en este artículo se utilizará el sistema binario, pero también se puede utilizar cualquier otra base (así como otras posibilidades, como los números de Fibonacci ).

Si se utiliza el sistema binario, un conjunto de elementos se descompone en subconjuntos de tamaños con ${\displaystyle n}$

${\displaystyle 2^{i}*n_{i}}$

elementos donde es el bit -ésimo de en binario. Esto significa que si tiene el bit -ésimo igual a 0, el conjunto correspondiente no contiene ningún elemento. Cada uno de los subconjuntos tiene la misma propiedad que la estructura de datos estática original. Las operaciones realizadas en la nueva estructura de datos dinámica pueden implicar recorrer conjuntos formados por descomposición. Como resultado, esto agregará factor en oposición a las operaciones de estructura de datos estática, pero permitirá que se agregue la operación de inserción/eliminación. ${\displaystyle n_{i}}$ ${\displaystyle i}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle \log _{2}\left(n\right)}$ ${\displaystyle O(\log \left(n\right))}$

Kurt Mehlhorn demostró varias ecuaciones para la complejidad temporal de operaciones en las estructuras de datos dinamizadas según esta idea. Se enumeran algunas de estas ecuaciones.

Si

• ${\displaystyle P_{S}\left(n\right)}$Es el momento de construir la estructura de datos estática
• ${\displaystyle Q_{S}\left(n\right)}$Es el momento de consultar la estructura de datos estática
• ${\displaystyle Q_{D}\left(n\right)}$Es el momento de consultar la estructura de datos dinámica formada por descomposición.
• ${\displaystyle {\overline {I}}}$es el tiempo de inserción amortizado

entonces

• ${\displaystyle Q_{D}\left(n\right)=O\left(Q_{S}\left(n\right)\cdot \log \left(n\right)\right)}$
• ${\displaystyle {\overline {I}}=O\left(\left(P_{S}\left(n\right)/n\right)\cdot \log \left(n\right)\right).}$

Si es al menos polinomio , entonces . ${\displaystyle Q_{S}\left(n\right)}$ ${\displaystyle Q_{D}\left(n\right)=O\left(Q_{S}\left(n\right)\right)}$

Lectura adicional

• Kurt Mehlhorn, Estructuras de datos y algoritmos 3, . Una serie EATCS, vol. 3, Springer, 1984.