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

n が大きいとき、最も速く増加する計算量クラスはどれですか？

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

0 から k の範囲の n 個の整数に対する計数ソート（counting sort）の実行時間は何ですか？

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

平均実行時間は何を表しますか？

1. A最も一般的なコンピュータでの所要時間
2. Bサイズ n の入力の与えられた分布に対する期待所要時間
3. C平均的な長さの入力に対する所要時間
4. D最良の場合と最悪の場合の実行時間の中間の値

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

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

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

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

重みなしグラフでの幅優先探索（BFS）で求められるものはどれですか？

1. A始点ノードからの辺の数で測った最短経路
2. B最小全域木
3. C負の辺の重みを含むグラフでの最短経路
4. Dすべてのグラフにおけるトポロジカル順序

n が大きいとき、n! と 2ⁿ はどのように比較されますか？

1. A2ⁿ は n! より速く増加する
2. Bn! は 2ⁿ より速く増加する
3. C同じ速さで増加する
4. Dn! は O(n²) である

問題が NP 完全（NP-complete）であるのは、次のどの場合ですか？

1. A多項式時間で解ける
2. B解くことが不可能である
3. CNP に属し、すべての NP 問題が多項式時間でその問題に帰着できる
4. D停止問題のように、NP に属さないがすべての NP 問題より難しい