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

f(n) = Θ(g(n)) はどういう意味ですか？

1. Aすべての n について f は常に g より小さいので、g は上からは抑えるが下からは決して抑えない
2. Bf は g より真に速く増加する
3. Cf は g より真に遅く増加する
4. Df は g と同じ速さで増加し、上下から g の定数倍で抑えられる

増加の下界（lower bound）を表す記法はどれですか？

1. Ao（little o）
2. BΩ（Big Omega）
3. CO（Big O）
4. DΘ（Big Theta）

挿入ソート（insertion sort）の最悪時間計算量は何ですか？

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

到達可能な基底部をもたない再帰関数について、正しい記述はどれですか？

1. Aコールスタックがオーバーフローするまで自分自身を呼び続ける
2. BO(1) 時間で動作する
3. C自動的に 0 を返す
4. Dコンパイラが常にそれを、安全に終了するループに変換する

V 個の頂点と E 本の辺をもつグラフに対するベルマン－フォード法の時間計算量は何ですか？

1. AO(V³ × E)
2. BO(V × E)
3. CO(V + E)
4. DO(E log V)

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

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

決定不能な問題と扱いにくい問題の違いは何ですか？

1. A扱いにくい問題はどのアルゴリズムでも解けず、決定不能な問題は指数時間を必要とするだけである
2. Bどちらもアルゴリズムがまったくないことを意味する
3. C決定不能な問題は NP に属し、扱いにくい問題は P に属する
4. D決定不能な問題にはすべての入力で解くアルゴリズムがなく、扱いにくい問題にはあるが遅すぎる

トポロジカルソートが可能なのは、次のどのグラフだけですか？

1. A負の重みを持つグラフ
2. B完全グラフ
3. C無向グラフ
4. D有向非巡回グラフ（DAG）