フィボナッチ数 F(n) = F(n−1) + F(n−2) を定義どおりの単純な再帰で計算すると、計算量は指数時間になる。計算済みの値を表に記録して再利用する方法に変えたときの時間計算量はどれか。ここで、加算は定数時間で行えるものとする。

解説

正解は「$O(n)$」です。単純な再帰では、F(n−2) が F(n) と F(n−1) の両方から呼ばれるように同じ部分問題が何度も計算され、呼出し回数が指数的に増えます。計算済みの値を表に記録して再利用するメモ化や、F(0) から順に表を埋める動的計画法では、F(0) から F(n) までを1回ずつ計算すればよいので $O(n)$ になります。「$O(\log n)$」は、行列のべき乗を繰り返し2乗法で計算する特別な方法の計算量で、表に記録するだけでは達成できません。「$O(n^2)$」は、各値の計算でそれまでの値をすべて見直すような場合の計算量です。「$O(2^n)$」は、単純な再帰のままの計算量の目安です。