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

無料で印刷できるアルゴリズムと計算量のワークシート：やさしい問題から試験レベルまで 8 問、解答つき。印刷するか PDF で保存できます。

新しいワークシートヒントつきでオンライン練習

先生方へ： 授業で自由に印刷・コピーしてお使いいただけます。新しいワークシートごとに数値が変わり、専用の解答が付きます。授業ページに ExamProblems へのリンクを載せていただけると嬉しいです。

名前: ____________________   日付: ____________

1.やさしい

ある問題が通常「扱いやすい（tractable）」と呼ばれるのはどのような場合ですか？

  1. A多項式時間で解ける場合
  2. B解がない場合
  3. C定数時間で解ける場合
  4. Dあらゆる可能性を試すことでしか解けない場合
2.やさしい

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

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

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

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

クイックソートの最悪時間計算量は何ですか？

  1. AO(n)
  2. BO(log n)
  3. CO(n²)
  4. DO(n log n)
5.ふつう

活動選択問題で、重ならない活動の数を常に最大にする貪欲な規則はどれですか？

  1. A最も短い活動から選ぶ
  2. B最も早く始まる活動を選ぶ
  3. C最も早く終わる活動を選び、両立する活動で繰り返す
  4. D重なりの最も少ない活動を先に選び、両立する活動で繰り返す
6.ふつう

漸化式 T(n) = T(n − 1) + O(1) の解は何ですか？

  1. AO(n)
  2. BO(n²)
  3. CO(log n)
  4. DO(2ⁿ)
7.むずかしい

little-o 記法について正しい記述はどれですか？

  1. An² = o(n)
  2. Bどの関数も自分自身の little-o なので、n = o(n)
  3. C2n はゆっくり増加するので、2n = o(n)
  4. Dn = o(n²) だが、n は o(n) ではない
8.むずかしい

ハッシュテーブルの平均探索時間が O(1) なのに、最悪の場合は O(n) になるのはなぜですか？

  1. Aハッシュ関数が遅いから
  2. Bキーを先にソートする必要があるから
  3. C配列のアクセスが O(n) だから
  4. D多くのキーが同じバケットで衝突（collision）する可能性があるから

解答

  1. 1. A · 多項式時間で解ける場合
  2. 2. B · 入力が大きくなるにつれてアルゴリズムが必要とするメモリ量
  3. 3. A · サイズ n のすべての入力にわたる最大の所要時間
  4. 4. C · O(n²)
  5. 5. C · 最も早く終わる活動を選び、両立する活動で繰り返す
  6. 6. A · O(n)
  7. 7. D · n = o(n²) だが、n は o(n) ではない
  8. 8. D · 多くのキーが同じバケットで衝突（collision）する可能性があるから

ステップごとの詳しい解答：このトピックは examproblems.com で練習できます。