動的計画法（DP）を用いてフィボナッチ数列の第n項を求める場合，計算量のオーダはどれか。ここで，単純な再帰による計算量は O(2ⁿ) である。
ア O(1)
イ O(log n)
ウ O(n)
エ O(n²)
正解: ウ
要点: DPでは各部分問題を一度だけ計算してメモ化するため，O(n) で求まる。
この問題に出てくる用語
同じ回の前後の問題
- 令和4年度範囲 練習問題7: 再帰関数 f(n) が次のように定義されている。f(5) の値はいくつか。 f(n): n ≦ 1
- 令和4年度範囲 練習問題9: パイプライン処理において，ある命令の実行結果を次の命令が参照する必要がある場合に生じるハザードはどれ
テクノロジ系の他の問題
- 令和4年度範囲 練習問題9: パイプライン処理において，ある命令の実行結果を次の命令が参照する必要がある場合に生じるハザードはどれ
- 令和4年度範囲 練習問題10: マルチプロセッサ環境でキャッシュメモリのコヒーレンス（一貫性）を維持するために使用されるプロトコルは
- 令和4年度範囲 練習問題11: 仮想記憶方式において，ページフォールトが発生したとき，実記憶上に空きページ枠がない場合に行われる処理
- 令和4年度範囲 練習問題12: ページ置換アルゴリズムのうち，最も長い間参照されていないページを追い出す方式はどれか。
- 令和4年度範囲 練習問題13: デッドロックが発生するための必要条件として，適切でないものはどれか。
アプリで弱点分析つきの演習ができます