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

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

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

選択ソート（selection sort）はどのように動作しますか？

1. A配列を半分に分け、それらをマージする
2. B未ソート部分の最小値を繰り返し見つけ、それを先頭に交換する
3. C順序が逆になっている隣り合う要素を繰り返し交換する
4. Dシフトによって各要素を成長していくソート済み部分に挿入する

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

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

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

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

満杯になると容量を2倍にする動的配列に要素を追加する操作の償却（amortised）時間計算量は何ですか？

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

問題が最適部分構造をもつとはどういう意味ですか？

1. A問題を定数時間で解ける
2. Bすべての部分問題が同じサイズである
3. C問題の最適解がちょうど 1 つで、すべての部分問題がそれを共有しているから
4. D最適解を部分問題の最適解から構成できる

log(n!) について正しい評価はどれですか？

1. AΘ(n log n)
2. BΘ(n)
3. CΘ(n²)
4. DΘ(log n)

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

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