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

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

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

マージソート（merge sort）はどの設計戦略を用いていますか？

1. A動的計画法
2. B分割統治法
3. C貪欲法
4. D総当たり法

空間計算量（space complexity）が測るものはどれですか？

1. Aコンパイル後のプログラムファイルのディスク容量
2. Bコードの行数
3. Cコンピュータの物理的な大きさ
4. D入力が大きくなるにつれてアルゴリズムが必要とするメモリ量

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

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

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. AO(n²)
2. BO(n)
3. CO(n log n)
4. DO(log n)

ヘルド－カープの動的計画法アルゴリズムは巡回セールスマン問題を厳密に解きます。n 都市に対する実行時間は何ですか？

1. AO(n³)
2. BO(n² 2ⁿ)
3. CO(n!)
4. DO(2^n²)

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

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