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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

標準的な配列ベースのマージソートは、どれだけの追加メモリを使いますか？

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

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

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

アルゴリズムの最悪実行時間は何を表しますか？

  1. A最小の入力に対する所要時間
  2. B遅いコンピュータでの所要時間
  3. Cサイズ n のすべての入力にわたる最大の所要時間
  4. Dサイズ n のランダムな入力に対する期待所要時間
4.ふつう

長さ m と n の文字列の最長共通部分列を求める標準的な動的計画法の時間計算量は何ですか？

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

n 要素の配列を一度ソートし、その後 k 回の所属判定クエリに二分探索で答えます。全体のコストは何ですか？

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

ボトムアップの表を使って n 番目のフィボナッチ数を計算する時間計算量は何ですか？

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

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

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

巡回セールスマン問題はどのように分類されますか？

  1. A決定版は NP 完全で、最適化版は NP 困難である
  2. Bダイクストラ法がすべての都市を 1 回ずつ訪れて解くので、P に属する
  3. C決定版は P に属するが、最適化版は NP 完全である
  4. D決定不能である

解答

  1. 1. B · O(n)
  2. 2. B · O(log n)
  3. 3. C · サイズ n のすべての入力にわたる最大の所要時間
  4. 4. B · O(mn)
  5. 5. A · O(n log n + k log n)
  6. 6. B · O(n)
  7. 7. D · NP のすべての問題が多項式時間で解けることになり、P = NP となる
  8. 8. A · 決定版は NP 完全で、最適化版は NP 困難である

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