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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

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

  1. ABig Omega
  2. BBig Theta
  3. CLittle omega
  4. DBig O
2.やさしい

f(n) = Θ(g(n)) はどういう意味ですか？

  1. Af は g より真に速く増加する
  2. Bすべての n について f は常に g より小さいので、g は上からは抑えるが下からは決して抑えない
  3. Cf は g と同じ速さで増加し、上下から g の定数倍で抑えられる
  4. Df は g より真に遅く増加する
3.やさしい

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

  1. AO（Big O）
  2. Bo（little o）
  3. CΘ（Big Theta）
  4. DΩ（Big Omega）
4.ふつう

O(log n) のように、Big O で対数の底が通常省略されるのはなぜですか？

  1. A対数は常に整数に丸められるから
  2. B底は n が小さいときにしか問題にならないから
  3. C計算機科学のすべての対数は底が 10 なので、省略されているから
  4. D底の異なる対数は定数倍しか違わないから
5.ふつう

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

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

V 個の頂点と E 本の辺をもつグラフに対するベルマン－フォード法の時間計算量は何ですか？

  1. AO(V × E)
  2. BO(V³ × E)
  3. CO(V + E)
  4. DO(E log V)
7.むずかしい

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

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

for i = 1 to n: for (j = i; j ≤ n; j = j + i) do O(1) work の時間計算量は何ですか？

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

解答

  1. 1. D · Big O
  2. 2. C · f は g と同じ速さで増加し、上下から g の定数倍で抑えられる
  3. 3. D · Ω（Big Omega）
  4. 4. D · 底の異なる対数は定数倍しか違わないから
  5. 5. C · O(n³)
  6. 6. A · O(V × E)
  7. 7. B · ブール充足可能性問題（SAT）が NP 完全であること
  8. 8. D · O(n log n)

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