Timeline for When can I use dynamic programming to reduce the time complexity of my recursive algorithm?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 16, 2015 at 8:25 | comment | added | Raphael | Correction: evalutation DP-recurrences naively can still be (a lot) faster than brute force; cf. here. | |
| May 25, 2012 at 16:01 | comment | added | Raphael | @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. | |
| May 25, 2012 at 15:46 | comment | added | edA-qa mort-ora-y | 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. | |
| May 25, 2012 at 15:27 | comment | added | Raphael | @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. | |
| May 25, 2012 at 12:59 | comment | added | svick | 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? | |
| May 25, 2012 at 11:10 | history | answered | Raphael | CC BY-SA 3.0 |