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

アルゴリズムの最悪実行時間は何を表しますか？

1. A最小の入力に対する所要時間
2. Bサイズ n のすべての入力にわたる最大の所要時間
3. C遅いコンピュータでの所要時間
4. Dサイズ n のランダムな入力に対する期待所要時間

再帰とは何ですか？

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

O(2ⁿ) の増加は何と呼ばれますか？

1. A対数的
2. B指数的
3. C多項式的
4. D線形

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

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

プリム法は最小全域木をどのように構築しますか？

1. A開始頂点から 1 本の木を成長させ、木から出る最も安い辺を加える
2. Bすべての辺を重みでソートし、森の中で閉路をつくる場合を除いて 1 本ずつ加える
3. C閉路がなくなるまで最も高い辺を取り除く
4. D幅優先探索を実行し、BFS 木を残す

問題が最適部分構造をもつとはどういう意味ですか？

1. A最適解を部分問題の最適解から構成できる
2. B問題の最適解がちょうど 1 つで、すべての部分問題がそれを共有しているから
3. C問題を定数時間で解ける
4. Dすべての部分問題が同じサイズである

n が大きいとき、n! と 2ⁿ はどのように比較されますか？

1. An! は O(n²) である
2. B2ⁿ は n! より速く増加する
3. C同じ速さで増加する
4. Dn! は 2ⁿ より速く増加する

カラツバ乗算は T(n) = 3T(n/2) + O(n) を満たします。この解は何ですか？

1. AΘ(n²)
2. BΘ(n^{log₂ 3})、約 n^1.585
3. CΘ(n log n)
4. DΘ(n³)