In computer science, dynamic problems involve changing input data and require designing efficient algorithms and data structures that support queries while handling updates like insertion, deletion, or modification. Key complexity measures include space used for storage, initialization time to build the structure, insertion and deletion times to update it, and query time to retrieve information. Dynamic algorithms address these computations, adapting static problems—those with fixed input—into dynamic versions that reflect real-time changes, enhancing flexibility and efficiency when managing evolving data sets.
Special cases
Incremental algorithms, or online algorithms, are algorithms in which only additions of elements are allowed, possibly starting from empty/trivial input data.
Decremental algorithms are algorithms in which only deletions of elements are allowed, starting with the initialization of a full data structure.
If both additions and deletions are allowed, the algorithm is sometimes called fully dynamic.
Examples
Maximal element
Static problem For a set of N numbers find the maximal one.The problem may be solved in O(N) time.
Dynamic problem For an initial set of N numbers, dynamically maintain the maximal one when insertions and deletions are allowed.This is just the priority queue maintenance problem allowing for insertions and deletions; it can be solved, for example, using a binary heap in O ( log N ) {\displaystyle O(\log N)} time for an update and O ( 1 ) {\displaystyle O(1)} time for a query, with O ( N ) {\displaystyle O(N)} setup time (i.e., the initial processing of the data). Note that the value of N may change during the life of the structure.
Graphs
Given a graph, maintain its parameters, such as connectivity, maximal degree, shortest paths, etc., when insertion and deletion of its edges are allowed.1
Examples:
- There is an algorithm that maintains the minimum spanning forest of a weighted, undirected graph, subject to edge deletions and insertions, in O ( n 1 / 2 ) {\displaystyle O(n^{1/2})} time per update.2
- There is an algorithm that maintains the minimum spanning forest of a weighted, undirected graph, subject to edge deletions and insertions, in O ( n 1 / 3 log n ) {\displaystyle O(n^{1/3}\log n)} amortized time per update.3
See also
References
D. Eppstein, Z. Galil, and G. F. Italiano. "Dynamic graph algorithms". In CRC Handbook of Algorithms and Theory of Computation, Chapter 22. CRC Press, 1997. /wiki/D._Eppstein ↩
Eppstein, David; Italiano, Giuseppe; Nissenzweig, Amnon (1997). "Sparsification—a technique for speeding up dynamic graph algorithms". Journal of the ACM. 44 (5): 669–696. ↩
Henzinger, Monika; King, Valerie (2001). "Maintaining minimum spanning forests in dynamic graphs". SIAM Journal on Computing. 31 (2): 364–374. ↩