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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

3n² + 5n + 2 の Big O は何ですか？

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

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

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

平均実行時間は何を表しますか？

  1. A最良の場合と最悪の場合の実行時間の中間の値
  2. B最も一般的なコンピュータでの所要時間
  3. C平均的な長さの入力に対する所要時間
  4. Dサイズ n の入力の与えられた分布に対する期待所要時間
4.ふつう

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

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

クイックソートの最悪時間計算量は何ですか？

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

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

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

n が大きいとき、n! と 2ⁿ はどのように比較されますか？

  1. An! は 2ⁿ より速く増加する
  2. B同じ速さで増加する
  3. Cn! は O(n²) である
  4. D2ⁿ は n! より速く増加する
8.むずかしい

V 個の頂点と E 本の辺をもつグラフで、二分ヒープを用いたダイクストラ法の実行時間は何ですか？

  1. AO((V + E) log V)
  2. BO(V × E)
  3. CO(V³)
  4. DO(V + E)

解答

  1. 1. A · O(n²)
  2. 2. D · 配列がソートされていること
  3. 3. D · サイズ n の入力の与えられた分布に対する期待所要時間
  4. 4. C · O(n)
  5. 5. A · O(n²)
  6. 6. B · O(n)
  7. 7. A · n! は 2ⁿ より速く増加する
  8. 8. A · O((V + E) log V)

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