Memoization

noun

say it: “mem-oh-ih-ZAY-shun” /ˌmɛmoʊɪˈzeɪʃən/

Keeping each answer the first time a function works it out, and looking it up every time after that instead of working it out again.

What is memoization?

Memoization (from memo, a note to yourself) keeps each answer the first time a function works it out, and looks it up every time after that, like writing a sum on a sticky note. When a recursive function asks the same smaller question many times, it can turn O(2ⁿ) work into O(n).

In a sentence

  • “With memoization, counting the ways up 50 stairs took 99 calls instead of about 40 billion.”

Level: Journeyman · More Data Structures terms at this level

Updated

In other subjects