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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

アルゴリズムとは何ですか？

  1. A数値を格納するデータ構造
  2. B問題を解く、明確に定義された手順の有限の列
  3. C数式を書くために設計されたプログラミング言語
  4. Dグラフィカルなインターフェースをもつあらゆるコンピュータプログラム
2.やさしい

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

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

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

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

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

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

素朴な再帰によるフィボナッチ（fib(n) = fib(n−1) + fib(n−2)）の時間計算量はどれですか？

  1. A対数時間
  2. B指数時間
  3. C定数時間
  4. D線形時間
6.ふつう

n 要素の配列に対するマージソートの再帰は何段階になりますか？

  1. A約 n
  2. B約 √n
  3. C約 log₂ n
  4. D約 n / 2
7.むずかしい

P と NP に関する記述として正しいものはどれですか？

  1. ANP の問題は高速に検証できない
  2. BNP は "not polynomial" を意味する
  3. CP に属するすべての問題は NP にも属する
  4. DP ≠ NP であることが証明されている
8.むずかしい

動的計画法で解く 0/1 ナップサック問題は O(nW) 時間かかります。これが擬多項式（pseudo-polynomial）と呼ばれるのはなぜですか？

  1. AW は数値なので、実行時間は W を書くのに使うビット数に対して指数的になるから
  2. Bn が常に小さいから
  3. Cアルゴリズムが乱択（randomised）で、実行時間が入力ごとに変わるから
  4. DW = 0 の場合にしか動作しないから

解答

  1. 1. B · 問題を解く、明確に定義された手順の有限の列
  2. 2. D · 線形
  3. 3. D · 実行時間が入力サイズとともに増加しない
  4. 4. C · O(2ⁿ)
  5. 5. B · 指数時間
  6. 6. C · 約 log₂ n
  7. 7. C · P に属するすべての問題は NP にも属する
  8. 8. A · W は数値なので、実行時間は W を書くのに使うビット数に対して指数的になるから

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