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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

ソート済み配列に対する二分探索（binary search）の時間計算量は何ですか？

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

アルゴリズムの最悪実行時間は何を表しますか？

  1. Aサイズ n のすべての入力にわたる最大の所要時間
  2. B最小の入力に対する所要時間
  3. Cサイズ n のランダムな入力に対する期待所要時間
  4. D遅いコンピュータでの所要時間
3.やさしい

二分探索は入力に何を要求しますか？

  1. A配列がソートされていること
  2. B配列の要素が 1000 個以下であること
  3. C配列の長さが 2 のべき乗であること
  4. D配列が正の数だけを含むこと
4.ふつう

漸化式 T(n) = T(n − 1) + O(n) の解は何ですか？

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

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

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

ボトムアップの表を使って n 番目のフィボナッチ数を計算する時間計算量は何ですか？

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

単方向連結リストでは、二分探索が O(log n) 時間にならないのはなぜですか？

  1. A連結リストはソートできないから
  2. B二分探索には少なくとも 2 倍のメモリが必要だから
  3. C連結リストのノードでの比較は遅いから
  4. Dインデックスによる直接アクセスがないので、中央の要素に到達するのに O(n) ステップかかるから
8.むずかしい

最後の 2 つの値だけを保持するループで n 番目のフィボナッチ数を計算する時間と領域のコストは何ですか？

  1. A時間 O(n)、領域 O(n)
  2. B時間 O(log n)、領域 O(n)
  3. C時間 O(n)、領域 O(1)
  4. D時間 O(2ⁿ)、領域 O(1)

解答

  1. 1. D · O(log n)
  2. 2. A · サイズ n のすべての入力にわたる最大の所要時間
  3. 3. A · 配列がソートされていること
  4. 4. C · O(n²)
  5. 5. C · O(n)
  6. 6. B · O(n)
  7. 7. D · インデックスによる直接アクセスがないので、中央の要素に到達するのに O(n) ステップかかるから
  8. 8. C · 時間 O(n)、領域 O(1)

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