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

平均実行時間は何を表しますか？

1. A最良の場合と最悪の場合の実行時間の中間の値
2. B最も一般的なコンピュータでの所要時間
3. C平均的な長さの入力に対する所要時間
4. Dサイズ n の入力の与えられた分布に対する期待所要時間

ピボットを選び、配列を小さい要素と大きい要素に分割するソートアルゴリズムはどれですか？

1. A挿入ソート
2. Bバブルソート
3. Cクイックソート（quicksort）
4. Dマージソート

log₂ 1024 はいくつですか？

1. A12
2. B512
3. C10
4. D32

for i = 1 to n: (j = 1; while j < n: j = j × 2) の時間計算量は何ですか？

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

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

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

あるクイックソートは常に最初の要素をピボットに使います。どの入力で最悪の振る舞いを示しますか？

1. Aすでにソートされている配列
2. Bすべての要素が異なる配列
3. Cランダムな順序の配列
4. D長さ 2 の配列

n が大きいとき、n! と 2ⁿ はどのように比較されますか？

1. A同じ速さで増加する
2. B2ⁿ は n! より速く増加する
3. Cn! は O(n²) である
4. Dn! は 2ⁿ より速く増加する

次の充足可能性問題のうち、多項式時間で解けることが知られているのはどれですか？

1. A回路充足可能性問題
2. B各節のリテラルがちょうど 3 個の 3-SAT
3. C各節のリテラルが高々 2 個の 2-SAT
4. D連言標準形の式に対する一般の SAT