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.
Problemas de búsqueda descomponible
Definimos problema de buscar el predicado partido en el set como . Problemaes descomponible si el conjunto se puede descomponer en subconjuntos y existe una operación de unificación de resultados tal que .
Descomposició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
elementos donde es el -th bit de en binario. Esto significa que si posee -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 implicar atravesarconjuntos formados por descomposición. Como resultado, esto agregará factor en lugar de las operaciones de estructura de datos estáticos, pero permitirá que se agreguen operaciones de inserción / eliminación.
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.
Si
= tiempo para construir la estructura de datos estáticos = tiempo para consultar la estructura de datos estáticos = tiempo para consultar la estructura dinámica de datos formada por descomposición = tiempo de inserción amortizado
luego
Si es al menos polinomio , entonces.
Otras lecturas
- Kurt Mehlhorn, Estructuras de datos y algoritmos 3 ,. Una serie EATCS, vol. 3, Springer, 1984.