Memoise - メモ化
一度計算した結果を覚えておいて、二度目以降は律義に再計算しないで、覚えていたものを再利用する
というアイディア．
律義に再計算するよりも、一度計算したものを覚えておいて、それを再利用する方が安価
という前提において最適化技法の１つとなる．
fib(0) = 1 fib(1) = 1 fib(n) = fib(n-1) + fib(n-2)
を例に説明している．これを素直に実装すると時間計算量 O(2^n)，空間計算量 O(1) となるが，メモ化する（過去の計算結果を全て覚えておく）と時間計算量 O(n)，空間計算量 O(n) となる．（ただし，フィボナッチ数列の再帰的定義の場合，直前の 2 つの値を覚えておくだけで時間計算量 O(n) を達成できるため，本当は空間計算量 O(1) で済む．）
この例のように，うまく使えば時間計算量のオーダー自体が改善できる可能性もあるので，メモ化の有用性は非常に高いと思われる．しかし，計算結果を再利用できる確率や計算結果を再利用するためのコストを考慮しないで闇雲にメモ化を適用しても，空間計算量がむやみに爆発したり，空間計算量が増える割に時間計算量が減らない（あるいは逆に増える）場合もあるだろう．
この内容を最初に見つけたサイトでは名称が memoise とは別の表記になっていた．ググっても関連ページがほとんど見つからないのでおかしいと思っていた．ちなみに，他のサイトでは「memoise, memoize, memoisation, memoization, メモイズ」などと表記されている場合がある．（英語の資料は memoi'z'{e,ation} の方が多そう．）
