メモ化再帰の計算量

定義 3.1 の設定のもとで、次の再帰手続き $\mathrm{solve}(s)$ を考える。

• 表 $T[s]$ が「未計算」でなければ $T[s]$ を返す。
• そうでなければ、$D(s) = (s_1, \ldots, s_k)$ の各要素に対して $\mathrm{solve}(s_i)$ を呼び、その結果に $g_s$ を適用した値を $T[s]$ に書き込んで返す。

このとき、$s_0 \in S$ から $G$ の辺を逆向きに辿って到達できる部分問題の集合を $R \subseteq S$（$s_0 \in R$）とすると、$\mathrm{solve}(s_0)$ は停止し、$V(s_0)$ を返す。その計算時間は $O\bigl(|R| + \sum_{s \in R} c(s)\bigr)$ であり、$R$ に属さない部分問題は一度も評価されない。