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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

すでにソート済みの配列に対する挿入ソートの最良時間計算量は何ですか？

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

n 個の数からなる未ソートの配列で最大値を見つける時間計算量は何ですか？

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

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

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

ワーシャル－フロイド法は何を、どれくらいの速さで計算しますか？

  1. Aすべての頂点対の間の最短経路を O(V³) で
  2. B1 つの始点から他のすべての頂点への最短経路を O(V + E) で
  3. C最小全域木を O(E log V) で
  4. Dトポロジカル順序を O(V²) で
5.ふつう

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

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

1、3、4 の硬貨で金額 6 をつくるとき、貪欲な「最大の硬貨から」方式は最適解と比べて何枚の硬貨を使いますか？

  1. A貪欲法は 3 枚、最適解は 3 枚
  2. B貪欲法は 2 枚、最適解は 2 枚
  3. C貪欲法は 3 枚、最適解は 2 枚
  4. D貪欲法は 4 枚、最適解は 3 枚
7.むずかしい

n 個の未ソート要素からボトムアップ法で二分ヒープを構築する時間計算量は何ですか？

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

動的計画法で解く 0/1 ナップサック問題は O(nW) 時間かかります。これが擬多項式（pseudo-polynomial）と呼ばれるのはなぜですか？

  1. AW = 0 の場合にしか動作しないから
  2. BW は数値なので、実行時間は W を書くのに使うビット数に対して指数的になるから
  3. Cアルゴリズムが乱択（randomised）で、実行時間が入力ごとに変わるから
  4. Dn が常に小さいから

解答

  1. 1. C · O(n)
  2. 2. A · O(n)
  3. 3. C · サイズ n の入力の与えられた分布に対する期待所要時間
  4. 4. A · すべての頂点対の間の最短経路を O(V³) で
  5. 5. A · O(n log n)
  6. 6. C · 貪欲法は 3 枚、最適解は 2 枚
  7. 7. D · O(n)
  8. 8. B · W は数値なので、実行時間は W を書くのに使うビット数に対して指数的になるから

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