解答つきアルゴリズムと計算量ワークシート

3n² + 5n + 2 の Big O は何ですか？

1. AO(n²)
2. BO(n³)
3. CO(5n)
4. DO(3n²)

分割統治アルゴリズムの 3 つのステップは何ですか？

1. A分割、統治、結合
2. Bソート、探索、返却
3. C読み込み、計算、書き出し
4. D推測、確認、反復

総当たり（brute-force）アルゴリズムとは何ですか？

1. A考えられるすべての候補解を試すアルゴリズム
2. B多数のプロセッサで動作するアルゴリズム
3. C常に再帰を使うアルゴリズム
4. D答えをランダムに推測するアルゴリズム

満杯になると容量を2倍にする動的配列に要素を追加する操作の償却（amortised）時間計算量は何ですか？

1. AO(n²)
2. BO(n)
3. CO(log n)
4. DO(1)

漸化式 T(n) = 2T(n/2) + O(1) の解は何ですか？

1. AO(n²)
2. BO(n)
3. CO(log n)
4. DO(n log n)

到達可能な基底部をもたない再帰関数について、正しい記述はどれですか？

1. A自動的に 0 を返す
2. BO(1) 時間で動作する
3. Cコンパイラが常にそれを、安全に終了するループに変換する
4. Dコールスタックがオーバーフローするまで自分自身を呼び続ける

2²ⁿ は O(2ⁿ) に属しますか？

1. Aいいえ。2²ⁿ は 2ⁿ よりゆっくり増加するから
2. Bいいえ。2²ⁿ = 4ⁿ であり、4ⁿ / 2ⁿ = 2ⁿ は限りなく大きくなるから
3. Cはい。どちらも指数的だから
4. Dはい。Big O では指数の定数倍は常に無視されるから

次の充足可能性問題のうち、多項式時間で解けることが知られているのはどれですか？

1. A連言標準形の式に対する一般の SAT
2. B各節のリテラルが高々 2 個の 2-SAT
3. C各節のリテラルがちょうど 3 個の 3-SAT
4. D回路充足可能性問題