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

再帰関数の基底部（base case）とは何ですか？

1. A再帰呼び出しより前に処理される、入力が最も大きい場合
2. B関数の最初の行
3. C最も多くのメモリを使う呼び出し
4. Dさらに再帰呼び出しをせずに直接答えが得られる場合

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

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

配列の要素にインデックスでアクセスするのにかかる時間は次のどれですか？

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

1、3、4 の硬貨で金額 6 をつくるとき、貪欲な「最大の硬貨から」方式は最適解と比べて何枚の硬貨を使いますか？

1. A貪欲法は 3 枚、最適解は 2 枚
2. B貪欲法は 4 枚、最適解は 3 枚
3. C貪欲法は 2 枚、最適解は 2 枚
4. D貪欲法は 3 枚、最適解は 3 枚

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

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

辺の重みが非負のグラフで、一つの始点からの最短経路を求めるアルゴリズムはどれですか？

1. AKruskal 法
2. B深さ優先探索（DFS）
3. CDijkstra 法
4. Dどの場合でも Bellman–Ford が必要

カラツバ乗算は 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

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

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