Блог пользователя mshereef

Dynamic Programming Memoization Time Complexity
Автор mshereef, история, 3 года назад, По-английски

I was watching this lecture from MIT on dynamic programming, at the 22nd minute, the lecturer said that the formula for calculating the time complexity for a recursive dynamic programming solution using memoization is equal to the number of subproblems * the time of each subproblem without the recursive work.

I am having trouble understanding why this formula is true.

I understand the time complexity of a bottom-up solution because the loops make it obvious, but this top-down using memoization I find a bit confusing.

So if anyone cane share an intuitive way of understanding this formula it would be great.

Thank you in advance.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Consider all the subproblems you will need for some problem(i.e. for fibo you need all of the subproblems from 0 to n). Let's say you write fibo like:

int fibo(int n)
{
    if(n<2)
        return n;
    return fibo(n-1)+fibo(n-2);
}

Without memoization the code has O(2^N) complexity, because you have ~2^N calls. However, when memoizing you don't calculate a subproblem multiple times, only once. So after you solve fibo(n-1) in some time complexity, fibo(n-2) is already calculated so it's time complexity is O(1), instead of O(2^N). Because one of the subproblems is calculated in O(1), it can be ignored, leaving us with just one call. That call has some complexity depending(only) on fibo(n-2), which is calculated based(only) on fibo(n-3), ... giving you the complexity for fibo(n)=O(n). This is because the subproblems needed aren't computed multiple times, only once, so the function's complexity is just the time it takes to merge the subproblems * the ammount of subproblems. In the case of fibo, merging is done in constant time and number of subproblems is n.

I hope it helped.

→ Ответить