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

ある O(n) アルゴリズムは n = 100 万で 3 秒かかります。n = 200 万ではおよそ何秒かかりますか？

1. A3 秒
2. B12 秒
3. C6 秒
4. D9 秒

次の実行時間のうち、多項式時間はどれですか？

1. AO(n!)
2. BO(2ⁿ)
3. CO(n³)
4. DO(nⁿ)

再帰とは何ですか？

1. A決して終わらないループ
2. Bソートの手法の一つ
3. Cより小さな入力に対して自分自身を呼び出す関数
4. Dデータ構造の一種

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

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

O(n²) のアルゴリズムは O(n³) でもあると言うのは正しいですか？

1. Aいいえ。n が大きいとき n³ は n² より小さいから
2. Bいいえ。Big O は常に関数の正確な増加率を述べなければならないから
3. Cはい。Big O は上界であり、n² は n³ より速く増加しないから
4. Dはい。ただし n が 100 より小さい場合に限る

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

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

ソート済み配列における比較に基づく探索が、最悪の場合 Ω(log n) 回の比較を必要とするのはなぜですか？

1. Aすべての要素を少なくとも一度比較しなければならないから
2. B二分探索が唯一可能なアルゴリズムであり、log₂ n 回の比較が必要だから
3. Cn 通りの結果をもつ決定木は、深さが少なくとも log₂ n でなければならないから
4. D比較 1 回ごとに対数時間がかかるから

決定不能な問題と扱いにくい問題の違いは何ですか？

1. A決定不能な問題にはすべての入力で解くアルゴリズムがなく、扱いにくい問題にはあるが遅すぎる
2. B扱いにくい問題はどのアルゴリズムでも解けず、決定不能な問題は指数時間を必要とするだけである
3. Cどちらもアルゴリズムがまったくないことを意味する
4. D決定不能な問題は NP に属し、扱いにくい問題は P に属する