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

ある問題が通常「扱いやすい（tractable）」と呼ばれるのはどのような場合ですか？

1. A定数時間で解ける場合
2. Bあらゆる可能性を試すことでしか解けない場合
3. C多項式時間で解ける場合
4. D解がない場合

挿入ソート（insertion sort）の最悪時間計算量は何ですか？

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

増加の下界（lower bound）を表す記法はどれですか？

1. AO（Big O）
2. BΩ（Big Omega）
3. CΘ（Big Theta）
4. Do（little o）

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

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

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

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

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

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

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

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

ナップサック問題のどの変種で、「重さあたりの価値の順に品物をとる」という貪欲な規則が常に最適解を与えますか？

1. A品物を分割できる分数ナップサック問題
2. B品物を必ず丸ごととらなければならない 0/1 ナップサック問題
3. C両方の変種
4. Dどちらの変種でもない