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

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

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

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

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

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

1. ABig O
2. BLittle omega
3. CBig Omega
4. DBig Theta

貪欲法（greedy algorithm）の説明として正しいものはどれですか？

1. A各ステップで局所的に最良の選択をする
2. B再帰のみを使用する
3. C可能なすべての解を試す
4. D常に最適解を与える

安定（stable）なソートアルゴリズムはどれですか？

1. A選択ソート（一般的な版）
2. Bヒープソート
3. Cマージソート
4. Dクイックソート（一般的なインプレース版）

ソート済み配列で、両端から 1 つずつポインタを内側へ動かして、和が目標値になる 2 つの要素を探します。時間計算量は何ですか？

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

単方向連結リストでは、二分探索が O(log n) 時間にならないのはなぜですか？

1. A二分探索には少なくとも 2 倍のメモリが必要だから
2. Bインデックスによる直接アクセスがないので、中央の要素に到達するのに O(n) ステップかかるから
3. C連結リストのノードでの比較は遅いから
4. D連結リストはソートできないから

カラツバ乗算は T(n) = 3T(n/2) + O(n) を満たします。この解は何ですか？

1. AΘ(n log n)
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n^{log₂ 3})、約 n^1.585