素朴な再帰フィボナッチの計算量
fib(n)=fib(n-1)+fib(n-2) をメモ化せずそのまま再帰で計算するとき、関数呼び出し回数の増え方(時間計算量)として最も適切なものはどれか。
解説を見る
同じ引数の計算を何度も重複して行うため、呼び出し回数は約 φ^n(φ≈1.618)で増え、オーダーとしては指数時間 O(2^n) 程度になる。メモ化や動的計画法で重複計算を除くと O(n) に改善できる。
誤答の解説
BO(n) はメモ化・反復版の計算量。素朴な再帰は重複呼び出しで指数的に膨らむ。
CO(log n) は二分探索などの特性。加算を繰り返す本問には当てはまらない。
DO(n^2) でも足りず、実際はそれより速く増える指数オーダーになる。
ヒント
・同じ fib(k) が何度も再計算されることに注目する。
・呼び出しの木が枝分かれし続ける。