アルゴリズム・プログラミング応用問題
動的計画法でフィボナッチ数列を計算する場合、素直な再帰実装と比べて計算量はどのように変化するか。なお、fib(n)=fib(n-1)+fib(n-2)、fib(0)=0、fib(1)=1 とする。
A.時間計算量が O(2ⁿ) から O(n) に削減される← 正解
✓ 正解です。素直な再帰は同じ部分問題を指数回再計算し O(2ⁿ) ですが、メモ化により各部分問題を1回だけ計算する O(n) に削減されます。
B.時間計算量が O(n²) から O(n log n) に削減される
✗ 素直な再帰フィボナッチの計算量は O(n²) ではなく O(2ⁿ) です。出発点が誤っています。
C.時間計算量は変わらないが、空間計算量が O(n) から O(1) に削減される
✗ 動的計画法（メモ化再帰・ボトムアップ）は時間計算量も大幅に改善します。時間が変わらないという記述は誤りです。
D.時間計算量が O(n log n) から O(n) に削減される
✗ 素直な再帰フィボナッチは O(n log n) ではなく O(2ⁿ) であるため、出発点の説明が誤っています。