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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

再帰関数の基底部（base case）とは何ですか？

  1. Aさらに再帰呼び出しをせずに直接答えが得られる場合
  2. B最も多くのメモリを使う呼び出し
  3. C関数の最初の行
  4. D再帰呼び出しより前に処理される、入力が最も大きい場合
2.やさしい

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

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

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

  1. A2 秒
  2. B8 秒
  3. C1 秒
  4. D4 秒
4.ふつう

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

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

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

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

for i = 1 to n: (j = 1; while j < n: j = j × 2) の時間計算量は何ですか？

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

ソート済み配列における比較に基づく探索が、最悪の場合 Ω(log n) 回の比較を必要とするのはなぜですか？

  1. An 通りの結果をもつ決定木は、深さが少なくとも log₂ n でなければならないから
  2. Bすべての要素を少なくとも一度比較しなければならないから
  3. C二分探索が唯一可能なアルゴリズムであり、log₂ n 回の比較が必要だから
  4. D比較 1 回ごとに対数時間がかかるから
8.むずかしい

クラス NP の定義として正しいものはどれですか？

  1. A証拠（certificate）が与えられれば、「はい」の答えを多項式時間で検証できる決定問題
  2. Bどのアルゴリズムでも解けない問題
  3. C多項式時間で解けない問題
  4. D多項式でない問題

解答

  1. 1. A · さらに再帰呼び出しをせずに直接答えが得られる場合
  2. 2. C · 実行時間が入力サイズとともに増加しない
  3. 3. D · 4 秒
  4. 4. A · O(n²)
  5. 5. A · O(log n)
  6. 6. B · O(n log n)
  7. 7. A · n 通りの結果をもつ決定木は、深さが少なくとも log₂ n でなければならないから
  8. 8. A · 証拠（certificate）が与えられれば、「はい」の答えを多項式時間で検証できる決定問題

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