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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

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

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

次の実行時間のうち、多項式時間はどれですか？

  1. AO(n!)
  2. BO(n³)
  3. CO(nⁿ)
  4. DO(2ⁿ)
3.やさしい

増加の上界（upper bound）を表す記法はどれですか？

  1. ALittle omega
  2. BBig O
  3. CBig Omega
  4. DBig Theta
4.ふつう

貪欲法（greedy algorithm）の説明として正しいものはどれですか？

  1. A各ステップで局所的に最良の選択をする
  2. B可能なすべての解を試す
  3. C再帰のみを使用する
  4. D常に最適解を与える
5.ふつう

満杯になると容量を2倍にする動的配列に要素を追加する操作の償却（amortised）時間計算量は何ですか？

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

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

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

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

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

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

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

解答

  1. 1. B · 分割、統治、結合
  2. 2. B · O(n³)
  3. 3. B · Big O
  4. 4. A · 各ステップで局所的に最良の選択をする
  5. 5. D · O(1)
  6. 6. A · O(n)
  7. 7. B · 各節のリテラルが高々 2 個の 2-SAT
  8. 8. B · ピボットを一様ランダムに選ぶ

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