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

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

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

分割統治アルゴリズムの 3 つのステップは何ですか？

1. Aソート、探索、返却
2. B推測、確認、反復
3. C分割、統治、結合
4. D読み込み、計算、書き出し

再帰とは何ですか？

1. Aソートの手法の一つ
2. Bデータ構造の一種
3. Cより小さな入力に対して自分自身を呼び出す関数
4. D決して終わらないループ

n 要素の配列に対するマージソートの再帰は何段階になりますか？

1. A約 √n
2. B約 n / 2
3. C約 n
4. D約 log₂ n

素朴な再帰によるフィボナッチ（fib(n) = fib(n−1) + fib(n−2)）の時間計算量はどれですか？

1. A対数時間
2. B線形時間
3. C指数時間
4. D定数時間

ワーシャル－フロイド法は何を、どれくらいの速さで計算しますか？

1. Aすべての頂点対の間の最短経路を O(V³) で
2. B最小全域木を O(E log V) で
3. Cトポロジカル順序を O(V²) で
4. D1 つの始点から他のすべての頂点への最短経路を O(V + E) で

2²ⁿ は O(2ⁿ) に属しますか？

1. Aいいえ。2²ⁿ は 2ⁿ よりゆっくり増加するから
2. Bいいえ。2²ⁿ = 4ⁿ であり、4ⁿ / 2ⁿ = 2ⁿ は限りなく大きくなるから
3. Cはい。Big O では指数の定数倍は常に無視されるから
4. Dはい。どちらも指数的だから

漸化式 T(n) = 2T(n/2) + n log n の解は何ですか？

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