Dynamic problem (algorithms)
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 set is modified, i.e., objects are inserted or deleted.
Problems of this class have the folloiwng measures of complexity
- Memory space to store the required data structure
- Initial construction time of 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
Many algorithmic problems stated in terms of fixed input data (called static problems in this context) have meaningful dynamic versions.
Example
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 is a simplified version of this dynamic problem, where one equires to delete only the maximal element. This version may do with simpler data structures.