フィボナッチ数 F(n) を、計算済みの値を保存するメモ化再帰で求めたとき、時間計算量はどれになりますか？

素朴な再帰では、F(n) の計算で F(n-1) と F(n-2) を呼び出し、同じ値を何度も計算し直すため、時間計算量は指数的（おおよそ O(2^n)）になります。メモ化を使うと、各 F(k) は一度だけ計算されて配列などに保存され、以降は保存値を参照するだけになります。k は 0 から n までの n+1 種類しかなく、各計算は定数時間なので、全体の時間計算量は O(n) になります。これは動的計画法の基本的な考え方です。