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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

n が大きくなるとき、最もゆっくり増加するのはどれですか？

  1. AO(n log n)
  2. BO(n²)
  3. CO(log n)
  4. DO(n)
2.やさしい

選択ソート（selection sort）はどのように動作しますか？

  1. A未ソート部分の最小値を繰り返し見つけ、それを先頭に交換する
  2. B配列を半分に分け、それらをマージする
  3. C順序が逆になっている隣り合う要素を繰り返し交換する
  4. Dシフトによって各要素を成長していくソート済み部分に挿入する
3.やさしい

増加の下界（lower bound）を表す記法はどれですか？

  1. AΘ（Big Theta）
  2. BO（Big O）
  3. Co（little o）
  4. DΩ（Big Omega）
4.ふつう

辺の重みが非負のグラフで、一つの始点からの最短経路を求めるアルゴリズムはどれですか？

  1. Aどの場合でも Bellman–Ford が必要
  2. BKruskal 法
  3. C深さ優先探索（DFS）
  4. DDijkstra 法
5.ふつう

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

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

比較に基づくソートの最悪の場合の下界はどれですか？

  1. AΩ(n)
  2. BΩ(n log n)
  3. CΩ(n²)
  4. DΩ(log n)
7.むずかしい

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

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

巡回セールスマン問題はどのように分類されますか？

  1. A決定版は P に属するが、最適化版は NP 完全である
  2. B決定不能である
  3. C決定版は NP 完全で、最適化版は NP 困難である
  4. Dダイクストラ法がすべての都市を 1 回ずつ訪れて解くので、P に属する

解答

  1. 1. C · O(log n)
  2. 2. A · 未ソート部分の最小値を繰り返し見つけ、それを先頭に交換する
  3. 3. D · Ω（Big Omega）
  4. 4. D · Dijkstra 法
  5. 5. A · O(n³)
  6. 6. B · Ω(n log n)
  7. 7. C · X が NP に属すること、および既知の NP 完全問題が多項式時間で X に帰着すること
  8. 8. C · 決定版は NP 完全で、最適化版は NP 困難である

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