Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that if satisfied by a recursive algorithm would imply that using dynamic programming will reduce the time complexity of the algorithm? When should I use dynamic programming?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Related question: Deciding on Sub-Problems for Dynamic Programming $\endgroup$– RaphaelCommented May 25, 2012 at 10:47
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
Dynamic programming is useful is your recursive algorithm finds itself reaching the same situations (input parameters) many times. There is a general transformation from recursive algorithms to dynamic programming known as memoization, in which there is a table storing all results ever calculated by your recursive procedure. When the recursive procedure is called on a set of inputs which were already used, the results are just fetched from the table. This reduces recursive Fibonacci to iterative Fibonacci.
Dynamic programming can be even smarter, applying more specific optimizations. For example, sometimes there is no need to store the entire table in memory at any given time.
answered May 25, 2012 at 0:41
-
$\begingroup$ The counter would then be that anytime the space complexity of the memoization is greater than the input data (perhaps just > O(N)), chances are dynamic programming is not going to help. That is, when you infrequently encounter the same situation. $\endgroup$ Commented May 25, 2012 at 5:26
-
2$\begingroup$ Memoisation != dynamic programming! $\endgroup$– RaphaelCommented May 25, 2012 at 10:47
-
1$\begingroup$ I don't think we're saying that, but the question indicates reducing time complexity. Dynamic programming on its own simply partitions the problem. Dynamic programming + memoization is a generic way to improve time complexity where possible. $\endgroup$ Commented May 25, 2012 at 11:33
-
$\begingroup$ @edA-qamort-ora-y: Right. I think it is important to point that out clearly, as apparently the OP confuses/mixes the concepts. $\endgroup$– RaphaelCommented May 25, 2012 at 15:28
$\begingroup$
$\endgroup$
5
If you just seek to speed up your recursive algorithm, memoisation might be enough. This is the technique of storing results of function calls so that future calls with the same parameters can just reuse the result. This is applicable if (and only if) your function
- does not have side effects and
- does only depend on its parameters (i.e. not on some state).
It will save you time if (and only if) the function is called with the same parameters over and over again. Popular examples include the recursive definition of the Fibonacci numbers, that is
$\qquad \begin{align} f(0) &= 0 \\ f(1) &= 1 \\ f(n+2) &= f(n+1) + f(n) \qquad ,\ n \geq 0 \end{align}$
When evaluated naively, $f$ is called exponentially often. With memoisation, $f(n)$ has always been computed by $f(n+1)$ already, thus only a linear number of calls remains.
Note that, in contrast, memoisation is next to useless for algorithms like merge sort: usually few (if any) partial lists are identical, and equality checks are expensive (sorting is only slightly more costly!).
In practical implementations, how you store results is of great import to performance. Using hash tables may be the obvious choice, but might break locality. If your parameters are non-negative integers, arrays are a natural choice but may cause huge memory overhead if you use only some entries. Therefore, memoisation is a tradeoff between effect and cost; whether it pays off depends on your specific scenario.
Dynamic programming is a completely other beast. It is applicable to problems with the property that
- it can be partitioned into subproblems (probably in more than one way),
- those subproblems can be solved independently,
- (optimal) solutions of those subproblems can be combined to (optimal) solutions of the original problem and
- subproblems have the same property (or are trivial).
This is usually (implicitly) implied when people invoke Bellman's Principle of Optimality.
Now, this only describes a class of problems that can be expressed by a certain kind of recursion. Evaluation of those is (often) efficient because memoisation can be applied to great effect (see above); usually, smaller subproblems occur as parts of many larger problems. Popular examples include edit distance and the Bellman-Ford algorithm.
-
$\begingroup$ Are you saying there are cases where dynamic programming will lead to better time complexity, but memoization wouldn't help (or at least not as much)? Do you have any examples? Or are you just saying that dynamic programming is useful only for a subset of problems where memoization is? $\endgroup$– svickCommented May 25, 2012 at 12:59
-
1$\begingroup$ @svick: Dynamic programming does not speed up anything per se, only if the DP recursion is evaluated with memoisation (which is usually (!) the case). Again: DP is a way to model problems in terms of a recursion, memoisation is a technique to speed up suitable recursive algorithms (no matter whether DP). It does not make sense to compare both directly. Of course you try to model a problem as DP because you expect to apply memoisation and therefore solve it more quickly than naive(r) approaches could. But a DP point of view does not always lead to the most efficient algorithm, either. $\endgroup$– RaphaelCommented May 25, 2012 at 15:27
-
$\begingroup$ If you have multiple processors available dynamic programming greatly improves real-world performance as you can parallelize the parts. It doesn't actually change the time complexity though. $\endgroup$ Commented May 25, 2012 at 15:46
-
$\begingroup$ @edA-qamort-ora-y: That is true for any recursion. However, it is not clear that this creates good speedup, because memoisation is less efficient over processor boundaries. $\endgroup$– RaphaelCommented May 25, 2012 at 16:01
-