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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

ある O(n) アルゴリズムは n = 100 万で 3 秒かかります。n = 200 万ではおよそ何秒かかりますか？

  1. A12 秒
  2. B9 秒
  3. C6 秒
  4. D3 秒
2.やさしい

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

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

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

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

for i = 1 to n: for j = 1 to i: do O(1) work の時間計算量は何ですか？

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

動的計画法（dynamic programming）が有効なのは、問題が次の性質を持つときです。

  1. A重複する部分問題と最適部分構造
  2. B部分問題がまったくないので、1 ステップで解ける
  3. Cランダムな入力のみ
  4. Dループが一つだけ
6.ふつう

O(log n) のように、Big O で対数の底が通常省略されるのはなぜですか？

  1. A計算機科学のすべての対数は底が 10 なので、省略されているから
  2. B対数は常に整数に丸められるから
  3. C底は n が小さいときにしか問題にならないから
  4. D底の異なる対数は定数倍しか違わないから
7.むずかしい

どんな入力に対してもクイックソートの期待（expected）実行時間を O(n log n) にする手法はどれですか？

  1. A左側にのみ再帰を使う
  2. Bクイックソートを実行する前に入力をソートする
  3. Cピボットを一様ランダムに選ぶ
  4. D常に先頭の要素を選ぶ
8.むずかしい

次の充足可能性問題のうち、多項式時間で解けることが知られているのはどれですか？

  1. A各節のリテラルが高々 2 個の 2-SAT
  2. B各節のリテラルがちょうど 3 個の 3-SAT
  3. C回路充足可能性問題
  4. D連言標準形の式に対する一般の SAT

解答

  1. 1. C · 6 秒
  2. 2. D · 線形
  3. 3. B · 分割、統治、結合
  4. 4. C · O(n²)
  5. 5. A · 重複する部分問題と最適部分構造
  6. 6. D · 底の異なる対数は定数倍しか違わないから
  7. 7. C · ピボットを一様ランダムに選ぶ
  8. 8. A · 各節のリテラルが高々 2 個の 2-SAT

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