メモ化
メモ化という用語は1968年にドナルド・ミッキーがラテン語の memorandum(覚えておく)から作った造語である。memorization(記憶、暗記)は同根語であってよく似ているが、メモ化という言葉は情報工学では特別な意味を持つ。
メモ化された関数は、以前の呼び出しの際の結果をそのときの引数と共に記憶しておき、後で同じ引数で呼び出されたとき、計算せずにその格納されている結果を返す。メモ化可能な関数は参照透過性を備えたものに限られる。すなわち、メモ化されたことで副作用が生じない場合に限られる。メモ化の実装ではルックアップテーブルなどの参照方式が使われるが、メモ化では参照されるテーブルの内容は必要に応じて格納されるという点で、通常のテーブル参照とは異なる。
メモ化は関数の時間コストを領域コストに交換して、時間コストを低減させる手段である。すなわち、メモ化された関数は速度の面で最適化され、記憶装置の領域という面ではより多く消費する。計算複雑性理論は、アルゴリズムの時間と領域のコストを扱う。全ての関数には時間と領域についての複雑性が定義される。
このようにトレードオフが発生するが、同様のトレードオフがある最適化とは異なる。というのも、演算子強度低減などの最適化はコンパイル時のものだが、メモ化は実行時の最適化であるためである。さらに言えば、演算子強度低減は例えば、乗算を加算の組合せで表すことで性能を改善しようとするもので、プラットフォームのアーキテクチャに深く依存している。一方、メモ化はプラットフォームからは独立した戦略である。