Dynamic Programming Memoization Time Complexity

Правка en1, от mshereef, 2021-09-09 19:12:47

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.

Теги #dynamic programing, #memoization, #optimization, #recursion

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский mshereef 2021-09-09 19:12:47 725 Initial revision (published)