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 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
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
- 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.