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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

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

  1. A1 秒
  2. B8 秒
  3. C4 秒
  4. D2 秒
2.やさしい

あるアルゴリズムの実行時間は O(n) です。この増加は何と呼ばれますか？

  1. A対数的
  2. B定数
  3. C2 乗
  4. D線形
3.やさしい

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

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

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

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

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

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

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

  1. Aどの場合でも Bellman–Ford が必要
  2. BDijkstra 法
  3. CKruskal 法
  4. D深さ優先探索（DFS）
7.むずかしい

カラツバ乗算は T(n) = 3T(n/2) + O(n) を満たします。この解は何ですか？

  1. AΘ(n²)
  2. BΘ(n3)
  3. CΘ(n log n)
  4. DΘ(nlog₂ 3)、約 n1.585
8.むずかしい

ヘルド－カープの動的計画法アルゴリズムは巡回セールスマン問題を厳密に解きます。n 都市に対する実行時間は何ですか？

  1. AO(n!)
  2. BO(n³)
  3. CO(2n²)
  4. DO(n² 2ⁿ)

解答

  1. 1. C · 4 秒
  2. 2. D · 線形
  3. 3. C · O(log n)
  4. 4. C · O(n²)
  5. 5. D · 底の異なる対数は定数倍しか違わないから
  6. 6. B · Dijkstra 法
  7. 7. D · Θ(nlog₂ 3)、約 n1.585
  8. 8. D · O(n² 2ⁿ)

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