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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

分割統治アルゴリズムの 3 つのステップは何ですか？

  1. A分割、統治、結合
  2. Bソート、探索、返却
  3. C読み込み、計算、書き出し
  4. D推測、確認、反復
2.やさしい

マージソートの最悪時間計算量は何ですか？

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

メモ化（memoisation）とは何ですか？

  1. A再帰を自動的に等価なループに変換し、コールスタックを不要にすること
  2. B関数が戻った後にメモリを解放すること
  3. Cコードの各行の横にコメントを書くこと
  4. D関数呼び出しの結果を保存し、同じ呼び出しにはメモリから答えること
4.ふつう

ある関数は n 回反復するループを 1 つ実行し、その後別に n 回反復するループをもう 1 つ実行します。時間計算量は何ですか？

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

k 進数で d 桁の n 個の整数に対する LSD 基数ソートの実行時間は何ですか？

  1. AO(n log n)
  2. BO(d(n + k))
  3. CO(dn log k)
  4. DO(n²)
6.ふつう

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

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

ある NP 完全問題に対する多項式時間アルゴリズムを誰かが見つけたら、何が導かれますか？

  1. ANP のすべての問題が多項式時間で解けることになり、P = NP となる
  2. B停止問題が決定可能になる
  3. Cすべての指数時間アルゴリズムがただちに線形時間で動くようになる
  4. Dその 1 つの問題だけが P に移る
8.むずかしい

1 回のインクリメントで多くのビットが反転することがあるとして、2 進カウンタのインクリメントのならしコストは何ですか？

  1. Aインクリメント 1 回あたり O(1)
  2. Bインクリメント 1 回あたり O(log n)
  3. Cインクリメント 1 回あたり O(n)
  4. Dインクリメント 1 回あたり O(n log n)

解答

  1. 1. A · 分割、統治、結合
  2. 2. A · O(n log n)
  3. 3. D · 関数呼び出しの結果を保存し、同じ呼び出しにはメモリから答えること
  4. 4. A · O(n)
  5. 5. B · O(d(n + k))
  6. 6. C · O(n²)
  7. 7. A · NP のすべての問題が多項式時間で解けることになり、P = NP となる
  8. 8. A · インクリメント 1 回あたり O(1)

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