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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

ピボットを選び、配列を小さい要素と大きい要素に分割するソートアルゴリズムはどれですか？

  1. Aマージソート
  2. B挿入ソート
  3. Cバブルソート
  4. Dクイックソート（quicksort）
2.やさしい

ソート済み配列に対する二分探索（binary search）の時間計算量は何ですか？

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

ある O(n²) アルゴリズムは n = 1000 で 1 秒かかります。n = 2000 ではおよそ何秒かかりますか？

  1. A8 秒
  2. B1 秒
  3. C2 秒
  4. D4 秒
4.ふつう

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

  1. AΩ(n)
  2. BΩ(n²)
  3. CΩ(log n)
  4. DΩ(n log n)
5.ふつう

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

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

重みなしグラフでの幅優先探索（BFS）で求められるものはどれですか？

  1. A始点ノードからの辺の数で測った最短経路
  2. Bすべてのグラフにおけるトポロジカル順序
  3. C最小全域木
  4. D負の辺の重みを含むグラフでの最短経路
7.むずかしい

問題が NP 完全（NP-complete）であるのは、次のどの場合ですか？

  1. A停止問題のように、NP に属さないがすべての NP 問題より難しい
  2. B多項式時間で解ける
  3. CNP に属し、すべての NP 問題が多項式時間でその問題に帰着できる
  4. D解くことが不可能である
8.むずかしい

新しい問題 X が NP 困難であることを示すには、何をしなければなりませんか？

  1. AX を多項式時間で検証できることを示す
  2. BX を多項式時間で既知の NP 困難な問題に帰着させる
  3. C既知の NP 困難な問題を多項式時間で X に帰着させる
  4. DX には小さな入力に対する多項式アルゴリズムがないことを示す

解答

  1. 1. D · クイックソート（quicksort）
  2. 2. D · O(log n)
  3. 3. D · 4 秒
  4. 4. D · Ω(n log n)
  5. 5. C · O(n³)
  6. 6. A · 始点ノードからの辺の数で測った最短経路
  7. 7. C · NP に属し、すべての NP 問題が多項式時間でその問題に帰着できる
  8. 8. C · 既知の NP 困難な問題を多項式時間で X に帰着させる

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