Dynamic problem (algorithms)
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 is usually stated as follows:
Problems of this class have the following measures of complexity
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.
Online algorithm
s present a special case of dynamic algorithms, in which only additions of elements are allowed, possibly starting from the empty/trivial input data.
The problem may be easily solved in O(N) time.
Dynamic problem : For an initial set of N numbers, dynamically 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.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
are problems stated in terms of the changing input data. In the most general form a problem in this category is 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.
Online algorithm
Online algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from...
s present a special case of dynamic algorithms, in which only additions of elements are allowed, possibly starting from the empty/trivial input data.
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, dynamically 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
Self-balancing binary search tree
In computer science, a self-balancing binary search tree is any node based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions....
. 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
Priority queue
A priority queue is an abstract data type in computer programming.It is exactly like a regular queue or stack data structure, but additionally, each element is associated with a "priority"....
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.