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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

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

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

それぞれ n 回実行される二重の入れ子ループを持つアルゴリズムの計算量は、通常どれですか？

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

log₂ 1024 はいくつですか？

  1. A32
  2. B10
  3. C512
  4. D12
4.ふつう

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

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

ならし解析（amortised analysis）は何を測りますか？

  1. A最悪の操作列にわたる操作 1 回あたりの平均コスト
  2. B操作列のどこかにある、最もコストの高い 1 回の操作のコスト
  3. Cランダムな入力に対する期待コスト
  4. D最良の入力に対するアルゴリズムのコスト
6.ふつう

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

  1. A指数時間
  2. B対数時間
  3. C定数時間
  4. D線形時間
7.むずかしい

シュトラッセンのアルゴリズムは、半分のサイズのブロックの再帰的な掛け算を 8 回ではなく 7 回にして行列を掛けます。実行時間は何ですか？

  1. AΘ(n² log n)
  2. BΘ(n³)
  3. CΘ(nlog₂ 7)、約 n2.81
  4. DΘ(n2)
8.むずかしい

マスター定理を用いると、T(n) = 8T(n/2) + O(n²) の解はどれですか？

  1. AΘ(n² log n)
  2. BΘ(n²)
  3. CΘ(n log n)
  4. DΘ(n³)

解答

  1. 1. D · O(n³)
  2. 2. D · O(n²)
  3. 3. B · 10
  4. 4. D · O(1)
  5. 5. A · 最悪の操作列にわたる操作 1 回あたりの平均コスト
  6. 6. A · 指数時間
  7. 7. C · Θ(nlog₂ 7)、約 n2.81
  8. 8. D · Θ(n³)

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