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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

n 個の要素を持つ未ソートの配列に対する線形探索（linear search）の時間計算量（最悪の場合）は何ですか？

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

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

  1. A2 乗
  2. B定数
  3. C対数的
  4. D線形
3.やさしい

log₂ 1024 はいくつですか？

  1. A12
  2. B512
  3. C10
  4. D32
4.ふつう

for i = 1 to n: for j = 1 to i: do O(1) work の時間計算量は何ですか？

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

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

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

ソート済み配列で、両端から 1 つずつポインタを内側へ動かして、和が目標値になる 2 つの要素を探します。時間計算量は何ですか？

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

停止問題（halting problem）が示していることはどれですか？

  1. A一部のプログラムは高速なコンピュータでより速く動作するので、停止するかどうかはハードウェアに依存するから
  2. Bループは避けるべきである
  3. Cすべてのプログラムと入力について、それが停止するかどうかを判定できるアルゴリズムは存在しない
  4. Dすべてのプログラムはいずれ停止する
8.むずかしい

22n は O(2ⁿ) に属しますか？

  1. Aはい。どちらも指数的だから
  2. Bいいえ。22n = 4ⁿ であり、4ⁿ / 2ⁿ = 2ⁿ は限りなく大きくなるから
  3. Cはい。Big O では指数の定数倍は常に無視されるから
  4. Dいいえ。22n は 2ⁿ よりゆっくり増加するから

解答

  1. 1. C · O(n)
  2. 2. D · 線形
  3. 3. C · 10
  4. 4. A · O(n²)
  5. 5. B · O(d(n + k))
  6. 6. D · O(n)
  7. 7. C · すべてのプログラムと入力について、それが停止するかどうかを判定できるアルゴリズムは存在しない
  8. 8. B · いいえ。22n = 4ⁿ であり、4ⁿ / 2ⁿ = 2ⁿ は限りなく大きくなるから

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