Definition: Save (memoize) a computed answer for possible later reuse, rather than recomputing the answer.
Note: The term comes from "memo": "A short note written as a reminder." [The American Heritage Dictionary of the English Language, © 1970, American Heritage Publishing] 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.6
n). 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;
set all elements of memo to zero;
fib(n) {
if n is 1 or 2, return 1;
if memo[n] is not zero, return memo[n];
memo[n] = fib(n-1) + fib(n-2);
return memo[n];
}
Source: NIST Dictionary of Algorithms, Data Structures, and Problems, a public domain resource.