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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

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

  1. ALittle omega
  2. BBig O
  3. CBig Theta
  4. DBig Omega
2.やさしい

ある O(n²) アルゴリズムは n = 1000 で 1 秒かかります。n = 2000 ではおよそ何秒かかりますか？

  1. A2 秒
  2. B8 秒
  3. C1 秒
  4. D4 秒
3.やさしい

配列の要素にインデックスでアクセスするのにかかる時間は次のどれですか？

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

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

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

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

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

ワーシャル－フロイド法は何を、どれくらいの速さで計算しますか？

  1. Aすべての頂点対の間の最短経路を O(V³) で
  2. B1 つの始点から他のすべての頂点への最短経路を O(V + E) で
  3. Cトポロジカル順序を O(V²) で
  4. D最小全域木を O(E log V) で
7.むずかしい

未ソートの配列から k 番目に小さい要素を選択することについて、正しい記述はどれですか？

  1. Aクイックセレクトは期待 O(n) で動作し、中央値の中央値法は最悪 O(n) を保証する
  2. B選択にはソートが必要なので、常に Ω(n log n) が必要である
  3. C選択は O(n²) でしか行えない
  4. Dクイックセレクトはピボットの片側だけで再帰するので、最悪でも O(log n) で動作する
8.むずかしい

決定問題 X が NP 完全であることを証明するには、どの 2 つのことを示さなければなりませんか？

  1. AX が P に属すること、および X が SAT に帰着すること
  2. BX が P の問題に帰着すること、および X が NP に属すること
  3. CX に多項式アルゴリズムがないこと、および X が決定可能であること
  4. DX が NP に属すること、および既知の NP 完全問題が多項式時間で X に帰着すること

解答

  1. 1. B · Big O
  2. 2. D · 4 秒
  3. 3. C · O(1)
  4. 4. B · O(n log n)
  5. 5. B · O(d(n + k))
  6. 6. A · すべての頂点対の間の最短経路を O(V³) で
  7. 7. A · クイックセレクトは期待 O(n) で動作し、中央値の中央値法は最悪 O(n) を保証する
  8. 8. D · X が NP に属すること、および既知の NP 完全問題が多項式時間で X に帰着すること

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