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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

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

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

マージソートの最悪時間計算量は何ですか？

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

あるループは i = 1 から始まり、i > n となるまで各反復で i を 2 倍にします。何回反復しますか？

  1. A約 n² 回
  2. B約 n 回
  3. C約 log₂ n 回
  4. D約 n / 2 回
4.ふつう

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

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

動的計画法（dynamic programming）が有効なのは、問題が次の性質を持つときです。

  1. A部分問題がまったくないので、1 ステップで解ける
  2. Bランダムな入力のみ
  3. C重複する部分問題と最適部分構造
  4. Dループが一つだけ
6.ふつう

1,000,000 要素のソート済み配列に対して、二分探索は最悪の場合およそ何回の比較を必要としますか？

  1. A約 100 回
  2. B約 20 回
  3. C約 500,000 回
  4. D約 1,000 回
7.むずかしい

巡回セールスマン問題はどのように分類されますか？

  1. Aダイクストラ法がすべての都市を 1 回ずつ訪れて解くので、P に属する
  2. B決定版は NP 完全で、最適化版は NP 困難である
  3. C決定不能である
  4. D決定版は P に属するが、最適化版は NP 完全である
8.むずかしい

ソート済み配列における比較に基づく探索が、最悪の場合 Ω(log n) 回の比較を必要とするのはなぜですか？

  1. An 通りの結果をもつ決定木は、深さが少なくとも log₂ n でなければならないから
  2. B比較 1 回ごとに対数時間がかかるから
  3. Cすべての要素を少なくとも一度比較しなければならないから
  4. D二分探索が唯一可能なアルゴリズムであり、log₂ n 回の比較が必要だから

解答

  1. 1. B · O(log n)
  2. 2. A · O(n log n)
  3. 3. C · 約 log₂ n 回
  4. 4. C · O(n²)
  5. 5. C · 重複する部分問題と最適部分構造
  6. 6. B · 約 20 回
  7. 7. B · 決定版は NP 完全で、最適化版は NP 困難である
  8. 8. A · n 通りの結果をもつ決定木は、深さが少なくとも log₂ n でなければならないから

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