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

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

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

ある操作が O(1) 時間で動作するとはどういう意味ですか？

1. A実行時間 1 秒あたりちょうど 1 要素を処理する
2. B一度しか実行できない
3. C実行時間が入力サイズとともに増加しない
4. D常にちょうど 1 秒かかる

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

1. A6 秒
2. B9 秒
3. C3 秒
4. D12 秒

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

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

動的計画法がマージソートを実質的に高速化しないのはなぜですか？

1. A動的計画法はグラフ問題にしか使えず、配列には使えないから
2. B部分問題が重複しないので、再利用するものがないから
3. Cマージソートはすでに O(n) だから
4. Dマージソートには再帰的な構造がないから

活動選択問題で、重ならない活動の数を常に最大にする貪欲な規則はどれですか？

1. A最も早く始まる活動を選ぶ
2. B最も短い活動から選ぶ
3. C重なりの最も少ない活動を先に選び、両立する活動で繰り返す
4. D最も早く終わる活動を選び、両立する活動で繰り返す

クラス P の定義として正しいものはどれですか？

1. A決定性アルゴリズムによって多項式時間で解ける決定問題
2. B解を多項式時間で検証できるが、見つけることは決してできない問題
3. Cどのコンピュータでも指数時間を必要とする問題
4. D並列に解くことができる問題

未ソートの配列から k 番目に小さい要素を選択することについて、正しい記述はどれですか？

1. A選択は O(n²) でしか行えない
2. Bクイックセレクトはピボットの片側だけで再帰するので、最悪でも O(log n) で動作する
3. Cクイックセレクトは期待 O(n) で動作し、中央値の中央値法は最悪 O(n) を保証する
4. D選択にはソートが必要なので、常に Ω(n log n) が必要である