View source for Dynamic problem (algorithms)

{{Distinguish|Dynamic programming}}
{{one source |date=April 2024}}
In [[computer science]], '''dynamic problems''' are problems stated in terms of changing input data. In its most general form, a problem in this category is usually stated as follows:
* Given a structure composed of objects, find efficient algorithms and data structures to answer certain queries about the structure, while also efficiently supporting update operations such as insertion, deletion or modification of objects in the structure.

Problems in this class have the following measures of complexity:
* '''Space'''{{snd}} the amount of [[Memory space (computational resource)|memory space]] required to store the data structure;
* '''Initialization time'''{{snd}} time required for the initial construction of the data structure;
* '''Insertion time'''{{snd}} time required for the update of the data structure when one more input element is added;
* '''Deletion time'''{{snd}} time required for the update of the data structure when an input element is deleted;
* '''Query time'''{{snd}} time required to answer a query;
* Other operations specific to the problem in question

The overall set of computations for a dynamic problem is called a '''dynamic algorithm'''.

Many algorithmic problems stated in terms of fixed input data (called '''static problems''' in this context and solved by '''static algorithms''') have meaningful dynamic versions.

==Special cases==
'''Incremental algorithms''', or [[online algorithm]]s, 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 <math>O(\log N)</math> time for an update and <math>O(1)</math> time for a query, with <math>O(N)</math> 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.<ref>[[D. Eppstein]], [[Z. Galil]], and [[Giuseppe F. Italiano|G. F. Italiano]].  "Dynamic graph algorithms". In ''CRC Handbook of Algorithms and Theory of Computation'', Chapter 22. CRC Press, 1997.</ref>

Examples:
* There is an algorithm that maintains the [[minimum spanning tree|minimum spanning forest]] of a weighted, undirected graph, subject to edge deletions and insertions, in <math>O(n^{1/2})</math> time per update.{{r|sparsification}}
* There is an algorithm that maintains the [[minimum spanning tree|minimum spanning forest]] of a weighted, undirected graph, subject to edge deletions and insertions, in <math>O(n^{1/3}\log n)</math> [[amortized]] time per update.{{r|HK2001}}

==See also==
* [[Dynamization]]
* [[Dynamic connectivity]]
* [[Kinetic data structure]]

==References==
{{Reflist|refs=<ref name="HK2001">{{Cite journal
 | last1 = Henzinger 
 | first1 = Monika 
 | last2 = King
 | first2 = Valerie
 | title =  Maintaining minimum spanning forests in dynamic graphs
 | journal = SIAM Journal on Computing
 | volume = 31
 | issue = 2
 | pages = 364-374
 | date = 
 | year = 2001
 | doi = 
 | pmid = 
 | url = 
}}</ref>
<ref name="sparsification">{{Cite journal
 | last1 = Eppstein
 | first1 = David
 | last2 = Italiano
 | first2 = Giuseppe
 | last3 = Nissenzweig
 | first3 = Amnon
 | title = Sparsification—a technique for speeding up dynamic graph algorithms
 | journal = Journal of the ACM
 | volume = 44
 | issue = 5
 | pages = 669-696
 | date = 
 | year = 1997
 | doi = 
 | pmid = 
 | url = 
}}</ref>
}}
[[Category:Computational complexity theory]]


{{Computer-science-stub}}