Memoization
Memoization is a technique used to speed up computer programs by caching intermediary answers for later reuse, rather than recomputing them. Memoization is a characteristic of dynamic programming. Memoization literally means "to put in memory" and is derived from the greek word memo.
Example
A naive program to compute Fibonacci numbers is
fib(n) {
if n is 1 or 2, return 1;
return fib(n-1) + fib(n-2);
}
Because fib() is recomputed over and over for the same argument, run time for the above is Ω(1.6n). If instead we memoize (save) the value of fib(n) the first time we compute it, the run time is Θ(n).
allocate array for memo, setting all entries to zero;
initialize memo[1] and memo[2] to 1;
fib(n) {
if memo[n] is not zero, return memo[n];
memo[n] = fib(n-1) + fib(n-2);
return memo[n];
}
Of course, computing Fibonacci numbers can be easily done in constant time (see Fibonacci numbers), but this illustrates the technique.
Some uses
Note: This article contains material taken from a public domain entry within the NIST Dictionary of Algorithms and Data Structures at http://www.nist.gov/dads/HTML/memoize.html
This article is a stub. You can help BambooWeb by .
