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

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

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

隣接リストで格納されたグラフに対する深さ優先探索の時間計算量は何ですか？

1. AO(V + E)
2. BO(E log V)
3. CO(V × E)
4. DO(V²)

標準的な配列ベースのマージソートは、どれだけの追加メモリを使いますか？

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

貪欲法（greedy algorithm）の説明として正しいものはどれですか？

1. A可能なすべての解を試す
2. B再帰のみを使用する
3. C常に最適解を与える
4. D各ステップで局所的に最良の選択をする

素朴な再帰によるフィボナッチ（fib(n) = fib(n−1) + fib(n−2)）の時間計算量はどれですか？

1. A対数時間
2. B線形時間
3. C指数時間
4. D定数時間

1,000,000 要素のソート済み配列に対して、二分探索は最悪の場合およそ何回の比較を必要としますか？

1. A約 100 回
2. B約 20 回
3. C約 1,000 回
4. D約 500,000 回

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

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

シュトラッセンのアルゴリズムは、半分のサイズのブロックの再帰的な掛け算を 8 回ではなく 7 回にして行列を掛けます。実行時間は何ですか？

1. AΘ(n²)
2. BΘ(n^{log₂ 7})、約 n^2.81
3. CΘ(n² log n)
4. DΘ(n³)