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

マージソート（merge sort）はどの設計戦略を用いていますか？

1. A動的計画法
2. B分割統治法
3. C総当たり法
4. D貪欲法

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

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

順序が誤っている隣接要素を繰り返し交換するソートアルゴリズムはどれですか？

1. Aマージソート（Merge sort）
2. Bクイックソート（Quicksort）
3. Cバブルソート（Bubble sort）
4. Dヒープソート（Heap sort）

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

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

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

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

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

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

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

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

2²ⁿ は O(2ⁿ) に属しますか？

1. Aいいえ。2²ⁿ = 4ⁿ であり、4ⁿ / 2ⁿ = 2ⁿ は限りなく大きくなるから
2. Bいいえ。2²ⁿ は 2ⁿ よりゆっくり増加するから
3. Cはい。どちらも指数的だから
4. Dはい。Big O では指数の定数倍は常に無視されるから