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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

すでにソート済みの配列に対する挿入ソートの最良時間計算量は何ですか？

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

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

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

3n² + 5n + 2 の Big O は何ですか？

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

比較に基づくソートの最悪の場合の下界はどれですか？

  1. AΩ(n log n)
  2. BΩ(n²)
  3. CΩ(log n)
  4. DΩ(n)
5.ふつう

V 個の頂点と E 本の辺をもつグラフに対するベルマン－フォード法の時間計算量は何ですか？

  1. AO(V × E)
  2. BO(V + E)
  3. CO(V³ × E)
  4. DO(E log V)
6.ふつう

1、3、4 の硬貨で金額 6 をつくるとき、貪欲な「最大の硬貨から」方式は最適解と比べて何枚の硬貨を使いますか？

  1. A貪欲法は 2 枚、最適解は 2 枚
  2. B貪欲法は 3 枚、最適解は 2 枚
  3. C貪欲法は 4 枚、最適解は 3 枚
  4. D貪欲法は 3 枚、最適解は 3 枚
7.むずかしい

little-o 記法について正しい記述はどれですか？

  1. An² = o(n)
  2. B2n はゆっくり増加するので、2n = o(n)
  3. Cn = o(n²) だが、n は o(n) ではない
  4. Dどの関数も自分自身の little-o なので、n = o(n)
8.むずかしい

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

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

解答

  1. 1. C · O(n)
  2. 2. C · 実行時間が入力サイズとともに増加しない
  3. 3. C · O(n²)
  4. 4. A · Ω(n log n)
  5. 5. A · O(V × E)
  6. 6. B · 貪欲法は 3 枚、最適解は 2 枚
  7. 7. C · n = o(n²) だが、n は o(n) ではない
  8. 8. B · クイックセレクトは期待 O(n) で動作し、中央値の中央値法は最悪 O(n) を保証する

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