Los problemas dinámicos en la teoría de la complejidad computacional son problemas planteados en términos de datos de entrada cambiantes. En la forma más general, un problema en esta categoría se suele plantear de la siguiente manera:
- Dada una clase de objetos de entrada, encuentre algoritmos y estructuras de datos eficientes para responder una determinada consulta sobre un conjunto de objetos de entrada cada vez que se modifican los datos de entrada, es decir, se insertan o eliminan objetos.
Los problemas de esta clase tienen las siguientes medidas de complejidad:
- Espacio : la cantidad de espacio de memoria necesaria para almacenar la estructura de datos;
- Tiempo de inicialización : tiempo necesario para la construcción inicial de la estructura de datos;
- Tiempo de inserción : tiempo necesario para actualizar la estructura de datos cuando se agrega un elemento de entrada más;
- Tiempo de eliminación : tiempo necesario para actualizar la estructura de datos cuando se elimina un elemento de entrada;
- Tiempo de consulta : tiempo necesario para responder una consulta;
- Otras operaciones específicas del problema en cuestión
El conjunto general de cálculos para un problema dinámico se denomina algoritmo dinámico .
Muchos problemas algorítmicos expresados en términos de datos de entrada fijos (llamados problemas estáticos en este contexto y resueltos por algoritmos estáticos ) tienen versiones dinámicas significativas.
Casos especiales
Los algoritmos incrementales , o algoritmos en línea , son algoritmos en los que solo se permiten adiciones de elementos, posiblemente a partir de los datos de entrada vacíos / triviales.
Los algoritmos decrementales son algoritmos en los que solo se permiten eliminaciones de elementos, comenzando con una inicialización de una estructura de datos completa.
Si se permiten tanto adiciones como eliminaciones, el algoritmo a veces se denomina completamente dinámico .
Ejemplos de
Elemento máximo
- Problema estático
- Para un conjunto de N números, encuentre el máximo.
El problema puede resolverse en O (N) tiempo.
- Problema dinámico
- Para un conjunto inicial de N números, mantenga dinámicamente el máximo cuando se permitan la inserción y las eliminaciones.
Una solución conocida para este problema es utilizar un árbol de búsqueda binario autoequilibrado . Ocupa espacio O (N), puede construirse inicialmente en el tiempo O (N log N) y proporciona tiempos de inserción, eliminación y consulta en O (log N).
- El problema del mantenimiento de la cola de prioridad
- Es una versión simplificada de este problema dinámico, donde se requiere eliminar solo el elemento máximo. Esta versión puede funcionar con estructuras de datos más simples.
Gráficos
Dado un gráfico, mantenga sus parámetros, como conectividad, grado máximo, caminos más cortos, etc., cuando se permite la inserción y eliminación de sus bordes. [1]
Ver también
Referencias
- ^ D. Eppstein , Z. Galil y GF Italiano . "Algoritmos de gráficos dinámicos". En CRC Handbook of Algorithms and Theory of Computation , Capítulo 22. CRC Press, 1997.