Dinamización

En informática , la dinamización es el proceso de transformar una estructura de datos estática en una dinámica . ^{[ 1 ]} Si bien las estructuras de datos estáticas pueden ofrecer una funcionalidad excelente y consultas rápidas, su utilidad es limitada debido a su incapacidad para crecer o encogerse 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 métodos uniformes para crear estructuras de datos dinámicas.

Definimos el problema${\displaystyle P}$de buscar el predicado${\displaystyle M}$partido en el set${\displaystyle S}$como${\displaystyle P(M,S)}$. Problema${\displaystyle P}$es descomponible si el conjunto${\displaystyle S}$puede descomponerse en subconjuntos${\displaystyle S_{i}}$y existe una operación${\displaystyle +}$de unificación de resultados tal que${\displaystyle P(M,S)=P(M,S_{0})+P(M,S_{1})+\dots +P(M,S_{n})}$.

La descomposición es un término utilizado en informática para dividir estructuras de datos estáticas en unidades más pequeñas de tamaño desigual. El principio básico es que cualquier número decimal puede representarse en cualquier otra base. Para 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 pueden utilizar otras bases (como los números de Fibonacci ).

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

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

elementos donde${\displaystyle n_{i}}$es el ${\displaystyle i}$-la parte de${\displaystyle n}$en binario. Esto significa que si${\displaystyle n}$tiene${\displaystyle i}$Si el bit -ésimo es 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${\displaystyle \log _{2}\left(n\right)}$conjuntos formados por descomposición. Como resultado, esto añadirá${\displaystyle O(\log \left(n\right))}$ factor en contraposición a las operaciones de estructura de datos estática pero permitirá agregar operaciones de inserción/eliminación.

Kurt Mehlhorn demostró varias ecuaciones para la complejidad temporal de las operaciones en las estructuras de datos dinamizadas según esta idea. Algunas de estas igualdades se enumeran a continuación.

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${\displaystyle Q_{S}\left(n\right)}$es al menos polinomial , entonces${\displaystyle Q_{D}\left(n\right)=O\left(Q_{S}\left(n\right)\right)}$.

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