Dinamización

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

Definimos el problema de buscar la coincidencia de predicados 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})}$

La descomposición es un término que se utiliza en informática para dividir las 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 puede traducirse en una representación en cualquier otra base. Para obtener más detalles sobre el tema, consulte Descomposición (informática) . En aras de la simplicidad, 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 usa el sistema binario, un conjunto de elementos se divide en subconjuntos de tamaños con ${\ Displaystyle n}$

elementos donde es el -ésimo bit de en binario. Esto significa que si tiene -th bit 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áticos original. Las operaciones realizadas en la nueva estructura de datos dinámicos pueden involucrar conjuntos transversales formados por descomposición. Como resultado, esto agregará factor a diferencia de las operaciones de estructura de datos estáticos, pero permitirá agregar 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 probó varias ecuaciones para la complejidad temporal de las operaciones sobre las estructuras de datos dinamizadas de acuerdo con esta idea. Se enumeran algunas de estas igualdades.