CODEWITHSUNDEEP
algorithmdynamic-programminginterpretation
lsc4719
lsc4719

Reputation: 17

book interpretation, about DP (Could you explain this text in other word?)

This is a paragraph of the book: Introduction to Algorithms, 3rd Edition. p.336

"These two approaches yield algorithms with the same asymptotic running time, expect in unusual circumstances where the top-down approach does not actually recurse to examine all possible subproblems. The bottom-up approach often has much better constant factors, since it has less overhead for procedure calls."

The Context : two approaches are first top-down + memoization(DP) and second bottom-up method.

I got a question for you one more. Does 'overhead' of function call mean every function call needs time? Even if we solve all subproblems, top-down takes more time because of the 'overhead'?

Upvotes: 0

Views: 130

Answers (1)

chiastic-security
chiastic-security

Reputation: 20520

A bottom-up approach to dynamic programming means solving all the small problems first, and then using them to find answers to the next smallest, and so on. So, for instance, if the solution to a problem of length n depends only on answers to problems of length n-1, you might start by putting in all the solutions for length 0, then you'd iteratively fill in solutions to length 1, 2, 3, and so on, each time using the answers you'd already calculated at the previous level. It is efficient in that it means you don't end up solving a sub-problem twice.

A top-down with memoization approach would look at it the other way. If you want the solution to a problem of length 10, then you do so recursively. You notice that it relies on (say) three problems of length 9, so you recursively solve them, and then you know the answer of length 10. But whenever you solve a sub-problem, you remember the answer, and whenever you need the answer to a sub-problem, you look first to see whether you've already solved it, and if you have, you return the cached answer.

The bottom-up approach is good in that it can be written iteratively (using for loops) rather than recursively, which means you don't run out of stack space on large problems, and loops are also faster. Its disadvantage is that you solve all the sub-problems, and you might not need them all to be solved in order to solve the large problem you want the answer to.

The top-down approach is slower if you need all the sub-problems solved anyway, because of the recursion overhead. But it is faster if the problem you're solving only needs a smallish subset of the sub-problems to be solved, because it only solves the ones that it needs.

It is essentially the same as the difference between eager evaluation (bottom up) and lazy evaluation (top down).

Upvotes: 5

Related Questions