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

マージソートの最悪時間計算量は何ですか？

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

f(n) = Θ(g(n)) はどういう意味ですか？

1. Aすべての n について f は常に g より小さいので、g は上からは抑えるが下からは決して抑えない
2. Bf は g より真に遅く増加する
3. Cf は g より真に速く増加する
4. Df は g と同じ速さで増加し、上下から g の定数倍で抑えられる

再帰とは何ですか？

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

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

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

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

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

1、3、4 の硬貨で金額 6 をつくるとき、貪欲な「最大の硬貨から」方式は最適解と比べて何枚の硬貨を使いますか？

1. A貪欲法は 3 枚、最適解は 2 枚
2. B貪欲法は 3 枚、最適解は 3 枚
3. C貪欲法は 4 枚、最適解は 3 枚
4. D貪欲法は 2 枚、最適解は 2 枚

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

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

little-o 記法について正しい記述はどれですか？

1. An = o(n²) だが、n は o(n) ではない
2. Bn² = o(n)
3. Cどの関数も自分自身の little-o なので、n = o(n)
4. D2n はゆっくり増加するので、2n = o(n)