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

標準的な配列ベースのマージソートは、どれだけの追加メモリを使いますか？

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

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

1. ABig Theta
2. BBig Omega
3. CBig O
4. DLittle omega

それぞれ n 回実行される二重の入れ子ループを持つアルゴリズムの計算量は、通常どれですか？

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

for i = 1 to n: for j = 1 to i: do O(1) work の時間計算量は何ですか？

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

1,000,000 要素のソート済み配列に対して、二分探索は最悪の場合およそ何回の比較を必要としますか？

1. A約 1,000 回
2. B約 20 回
3. C約 100 回
4. D約 500,000 回

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

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

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

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

ハッシュテーブルの平均探索時間が O(1) なのに、最悪の場合は O(n) になるのはなぜですか？

1. Aハッシュ関数が遅いから
2. B多くのキーが同じバケットで衝突（collision）する可能性があるから
3. C配列のアクセスが O(n) だから
4. Dキーを先にソートする必要があるから