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

総当たり（brute-force）アルゴリズムとは何ですか？

1. A常に再帰を使うアルゴリズム
2. B答えをランダムに推測するアルゴリズム
3. C考えられるすべての候補解を試すアルゴリズム
4. D多数のプロセッサで動作するアルゴリズム

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

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

n が大きくなるとき、最もゆっくり増加するのはどれですか？

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

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

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

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

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

標準的な 3 重ループで 2 つの n × n 行列を掛ける時間計算量は何ですか？

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

巡回セールスマン問題はどのように分類されますか？

1. A決定版は NP 完全で、最適化版は NP 困難である
2. Bダイクストラ法がすべての都市を 1 回ずつ訪れて解くので、P に属する
3. C決定版は P に属するが、最適化版は NP 完全である
4. D決定不能である

未ソートの配列から k 番目に小さい要素を選択することについて、正しい記述はどれですか？

1. Aクイックセレクトはピボットの片側だけで再帰するので、最悪でも O(log n) で動作する
2. B選択にはソートが必要なので、常に Ω(n log n) が必要である
3. C選択は O(n²) でしか行えない
4. Dクイックセレクトは期待 O(n) で動作し、中央値の中央値法は最悪 O(n) を保証する