NIST

memoization

(algorithmic technique)

Definition: Save (memoize) a computed answer for later reuse, rather than recomputing the answer.

See also dynamic programming.

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.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;
 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 logarithmic time (see Fibonacci numbers), but this illustrates the technique.

Author: PEB

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified Tue Jan 11 15:38:44 2005.
HTML page formatted Wed Oct 26 09:47:47 2005.

Cite this as:
Paul E. Black, "memoization", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/memoize.html

to NIST home page