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

ある O(n²) アルゴリズムは n = 1000 で 1 秒かかります。n = 2000 ではおよそ何秒かかりますか？

1. A4 秒
2. B1 秒
3. C2 秒
4. D8 秒

ある問題が通常「扱いやすい（tractable）」と呼ばれるのはどのような場合ですか？

1. A定数時間で解ける場合
2. B解がない場合
3. C多項式時間で解ける場合
4. Dあらゆる可能性を試すことでしか解けない場合

順序が誤っている隣接要素を繰り返し交換するソートアルゴリズムはどれですか？

1. Aクイックソート（Quicksort）
2. Bヒープソート（Heap sort）
3. Cバブルソート（Bubble sort）
4. Dマージソート（Merge sort）

比較に基づくソートの最悪の場合の下界はどれですか？

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

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

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

ならし解析（amortised analysis）は何を測りますか？

1. A操作列のどこかにある、最もコストの高い 1 回の操作のコスト
2. B最悪の操作列にわたる操作 1 回あたりの平均コスト
3. Cランダムな入力に対する期待コスト
4. D最良の入力に対するアルゴリズムのコスト

1 回のインクリメントで多くのビットが反転することがあるとして、2 進カウンタのインクリメントのならしコストは何ですか？

1. Aインクリメント 1 回あたり O(log n)
2. Bインクリメント 1 回あたり O(1)
3. Cインクリメント 1 回あたり O(n)
4. Dインクリメント 1 回あたり O(n log n)

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

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