Los problemas dinámicos en la teoría de la complejidad computacional son problemas planteados 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:
Los problemas de esta clase tienen las siguientes medidas de complejidad:
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.
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/triviales.
Los algoritmos decrementales son algoritmos en los que sólo 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 .
El problema puede resolverse en tiempo O(N).
Una solución bien 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).
Dado un gráfico, mantenga sus parámetros, como conectividad, grado máximo, caminos más cortos, etc., cuando se permita la inserción y eliminación de sus aristas. [1]