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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

ある問題が通常「扱いやすい（tractable）」と呼ばれるのはどのような場合ですか？

  1. Aあらゆる可能性を試すことでしか解けない場合
  2. B定数時間で解ける場合
  3. C解がない場合
  4. D多項式時間で解ける場合
2.やさしい

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

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

挿入ソート（insertion sort）の最悪時間計算量は何ですか？

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

あるクイックソートは常に最初の要素をピボットに使います。どの入力で最悪の振る舞いを示しますか？

  1. A長さ 2 の配列
  2. Bすべての要素が異なる配列
  3. Cすでにソートされている配列
  4. Dランダムな順序の配列
5.ふつう

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

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

クイックソートの最悪時間計算量は何ですか？

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

極大マッチングのすべての辺の両端点をとると頂点被覆が得られます。この被覆はどれくらいよいですか？

  1. A最小頂点被覆のサイズの高々 2 倍
  2. B最適解と比べた品質は不明
  3. C常に最小頂点被覆
  4. D最小値の高々 log n 倍
8.むずかしい

マスター定理を用いると、T(n) = 8T(n/2) + O(n²) の解はどれですか？

  1. AΘ(n³)
  2. BΘ(n² log n)
  3. CΘ(n²)
  4. DΘ(n log n)

解答

  1. 1. D · 多項式時間で解ける場合
  2. 2. A · 実行時間が入力サイズとともに増加しない
  3. 3. C · O(n²)
  4. 4. C · すでにソートされている配列
  5. 5. A · O(n³)
  6. 6. C · O(n²)
  7. 7. A · 最小頂点被覆のサイズの高々 2 倍
  8. 8. A · Θ(n³)

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