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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

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

  1. Ao（little o）
  2. BΩ（Big Omega）
  3. CO（Big O）
  4. DΘ（Big Theta）
2.やさしい

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

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

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

  1. A定数
  2. B線形
  3. C対数的
  4. D2 乗
4.ふつう

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

  1. A線形時間
  2. B定数時間
  3. C指数時間
  4. D対数時間
5.ふつう

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

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

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

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

挿入ソートはソート済みの入力に対して O(n) で動作します。これは比較ソートの Ω(n log n) の下界と矛盾しますか？

  1. Aいいえ。挿入ソートは比較ソートではないから
  2. Bいいえ。下界はすべての入力にわたる最悪の場合に適用されるのであって、すべての入力に適用されるわけではない
  3. Cはい。ただし 100 より短い配列の場合に限る
  4. Dはい。したがって下界は誤りである
8.むずかしい

log(n!) について正しい評価はどれですか？

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

解答

  1. 1. B · Ω（Big Omega）
  2. 2. C · O(1)
  3. 3. B · 線形
  4. 4. C · 指数時間
  5. 5. D · 最悪の操作列にわたる操作 1 回あたりの平均コスト
  6. 6. A · 各ステップで局所的に最良の選択をする
  7. 7. B · いいえ。下界はすべての入力にわたる最悪の場合に適用されるのであって、すべての入力に適用されるわけではない
  8. 8. D · Θ(n log n)

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