Hispanopedia WikiLos problemas dinámicos en la teoría de la complejidad computacional son problemas que se plantean en términos de cambios en los datos de entrada. En su forma más general, un problema de esta categoría suele plantearse de la siguiente manera:
- Dada una clase de objetos de entrada, encontrar algoritmos y estructuras de datos eficientes para responder a 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 la actualización de la estructura de datos cuando se agrega un elemento de entrada más;
- Tiempo de eliminación : tiempo necesario para la actualización de 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 planteados en términos de datos de entrada fijos (llamados problemas estáticos en este contexto y resueltos mediante 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 datos de entrada vacíos o triviales.
Los algoritmos decrementales son algoritmos en los que solo se permiten eliminaciones de elementos, comenzando con la 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
Elemento máximo
- Problema estático
- Para un conjunto de N números encuentre el máximo.
El problema puede resolverse en tiempo O(N).
- Problema dinámico
- Para un conjunto inicial de N números, mantener dinámicamente el máximo cuando se permiten inserciones y eliminaciones.
Una solución conocida para este problema es el uso de un árbol binario de búsqueda autoequilibrado . Ocupa un espacio de O(N), puede construirse inicialmente en un tiempo de 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, en el que se requiere eliminar únicamente el elemento máximo. Esta versión puede funcionar con estructuras de datos más simples.
Gráficos
Dado un gráfico, mantener sus parámetros, como conectividad, grado máximo, caminos más cortos, etc., cuando se permite la inserción y eliminación de sus aristas. [1]
Véase también
Referencias
- ^ D. Eppstein , Z. Galil y GF Italiano . "Algoritmos de grafos dinámicos". En CRC Handbook of Algorithms and Theory of Computation , Capítulo 22. CRC Press, 1997.
