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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

ある操作が O(1) 時間で動作するとはどういう意味ですか？

  1. A実行時間 1 秒あたりちょうど 1 要素を処理する
  2. B常にちょうど 1 秒かかる
  3. C実行時間が入力サイズとともに増加しない
  4. D一度しか実行できない
2.やさしい

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

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

n が大きいとき、最も速く増加する計算量クラスはどれですか？

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

貪欲法（greedy algorithm）の説明として正しいものはどれですか？

  1. A常に最適解を与える
  2. B各ステップで局所的に最良の選択をする
  3. C可能なすべての解を試す
  4. D再帰のみを使用する
5.ふつう

長さ m と n の文字列の最長共通部分列を求める標準的な動的計画法の時間計算量は何ですか？

  1. AO(mn)
  2. BO(m + n)
  3. CO(mn log n)
  4. DO(2m+n)
6.ふつう

ボトムアップの表を使って n 番目のフィボナッチ数を計算する時間計算量は何ですか？

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

決定問題 X が NP 完全であることを証明するには、どの 2 つのことを示さなければなりませんか？

  1. AX が P の問題に帰着すること、および X が NP に属すること
  2. BX が P に属すること、および X が SAT に帰着すること
  3. CX に多項式アルゴリズムがないこと、および X が決定可能であること
  4. DX が NP に属すること、および既知の NP 完全問題が多項式時間で X に帰着すること
8.むずかしい

クック－レビンの定理は何を確立しましたか？

  1. Aブール充足可能性問題（SAT）が NP 完全であること
  2. BP が NP と等しくないこと
  3. Cすべての NP 問題が指数時間で解けること
  4. D停止問題が決定不能であること

解答

  1. 1. C · 実行時間が入力サイズとともに増加しない
  2. 2. B · 分割統治法
  3. 3. B · O(2ⁿ)
  4. 4. B · 各ステップで局所的に最良の選択をする
  5. 5. A · O(mn)
  6. 6. B · O(n)
  7. 7. D · X が NP に属すること、および既知の NP 完全問題が多項式時間で X に帰着すること
  8. 8. A · ブール充足可能性問題（SAT）が NP 完全であること

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