Memoization in Simple Terms

w7r.blogspot.com

Memoization in real talk

Memoization is a strategy for solving a problem which requires repeated work in some manner. Instead of actually repeating the same work, we memorize it (by we I mean the running program). The program writes memos (reminders) to itself, and then before trying to perform work, it checks to see if there is a memo for the particular problem. The time spent looking at the memos is relatively small when using a special data structure known as the HashTable, but in many cases a flat array, or list of values suffices. If the memo-lookup doesn't exist for a set of parameters, then you will calculate the solution for that set of parameters and then store the result in the hashtable or list for any future calls with that same parameter set.

Why use memoization?

It can turn a recursive function from exponential runtime to something much simpler such as NlogN runtime. Big Oh of k O(k). It is important to remember that the decision of structure for holding "cached" (previously stored) results will effect the program runtime dramatically.

The Hidden Cost

The hidden cost of memoization is the space required to store all of the memos in their data structure. When space is scarce, memoization would not be a good solution.