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

n 個の要素を持つ未ソートの配列に対する線形探索（linear search）の時間計算量（最悪の場合）は何ですか？

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

二分探索は入力に何を要求しますか？

1. A配列が正の数だけを含むこと
2. B配列の長さが 2 のべき乗であること
3. C配列の要素が 1000 個以下であること
4. D配列がソートされていること

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

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

漸化式 T(n) = T(n − 1) + O(n) の解は何ですか？

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

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

1. Aどの場合でも Bellman–Ford が必要
2. BKruskal 法
3. C深さ優先探索（DFS）
4. DDijkstra 法

重みなしグラフでの幅優先探索（BFS）で求められるものはどれですか？

1. A最小全域木
2. Bすべてのグラフにおけるトポロジカル順序
3. C負の辺の重みを含むグラフでの最短経路
4. D始点ノードからの辺の数で測った最短経路

挿入ソートはソート済みの入力に対して O(n) で動作します。これは比較ソートの Ω(n log n) の下界と矛盾しますか？

1. Aはい。ただし 100 より短い配列の場合に限る
2. Bいいえ。下界はすべての入力にわたる最悪の場合に適用されるのであって、すべての入力に適用されるわけではない
3. Cはい。したがって下界は誤りである
4. Dいいえ。挿入ソートは比較ソートではないから

マスター定理を用いると、T(n) = 8T(n/2) + O(n²) の解はどれですか？

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