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

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

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

n 個の数からなる未ソートの配列で最大値を見つける時間計算量は何ですか？

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

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

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

標準的な 3 重ループで 2 つの n × n 行列を掛ける時間計算量は何ですか？

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

あるクイックソートは常に最初の要素をピボットに使います。どの入力で最悪の振る舞いを示しますか？

1. Aすでにソートされている配列
2. Bすべての要素が異なる配列
3. Cランダムな順序の配列
4. D長さ 2 の配列

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

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

次の充足可能性問題のうち、多項式時間で解けることが知られているのはどれですか？

1. A回路充足可能性問題
2. B各節のリテラルが高々 2 個の 2-SAT
3. C連言標準形の式に対する一般の SAT
4. D各節のリテラルがちょうど 3 個の 3-SAT

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

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