Dynamic problem (algorithms)
From Wikipedia, the free encyclopedia
Dynamic problems in computational complexity theory are problems stated in terms of the changing input data. In the most general form a problem in this category usually stated as follows:
- Given a class of input objects, find efficient algorithms and data structures to answer a certain query about a set of input objects each time the input data is modified, i.e., objects are inserted or deleted.
Problems of this class have the following measures of complexity
- Memory space to store the required data structure
- Initial construction time for the data structure
- Insertion time, time required for the update of the data structure when one more input element is added
- Deletion time, time required for the update of the data structure when an input element is deleted
- Query time: time required to answer
- 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.
A special case of dynamic problems/dynamic algoritms are online algorithms, in which only additions of elements are allowed, possibly starting from the empty/trivial input data.
Contents |
[edit] Examples
[edit] Maximal element
- Static problem
- For a set of N numbers find the maximal one.
The problem may be easily solved in O(N) time.
- Dynamic problem
- For an initial set of N numbers, dynamicall maintain the maximal one when insertion and deletions are allowed.
A well-known solution for this problem is using a self-balancing binary search tree. It takes space O(N), may be initially constructed in time O(N log N) and provides insertion, deletion and query times in O(log N).
- The priority queue maintenance problem
- It is a simplified version of this dynamic problem, where one requires to delete only the maximal element. This version may do with simpler data structures.
[edit] 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]
[edit] See also
[edit] 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.
