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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

O(2ⁿ) の増加は何と呼ばれますか？

  1. A指数的
  2. B多項式的
  3. C線形
  4. D対数的
2.やさしい

メモ化（memoisation）とは何ですか？

  1. Aコードの各行の横にコメントを書くこと
  2. B関数呼び出しの結果を保存し、同じ呼び出しにはメモリから答えること
  3. C再帰を自動的に等価なループに変換し、コールスタックを不要にすること
  4. D関数が戻った後にメモリを解放すること
3.やさしい

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

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

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

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

多くのライブラリのソート関数が、非常に小さな部分配列では挿入ソートに切り替えるのはなぜですか？

  1. A再帰アルゴリズムは 10 要素未満の配列を扱えないから
  2. B挿入ソートは最悪の場合 O(n log n) だから
  3. C挿入ソートはオーバーヘッドが小さく、小さな入力やほぼソート済みの入力で速いから
  4. D大きな入力では、挿入ソートは他のどのソートアルゴリズムよりメモリが少なくて済むから
6.ふつう

素朴な再帰によるフィボナッチ（fib(n) = fib(n−1) + fib(n−2)）の時間計算量はどれですか？

  1. A定数時間
  2. B対数時間
  3. C指数時間
  4. D線形時間
7.むずかしい

log(n!) について正しい評価はどれですか？

  1. AΘ(n)
  2. BΘ(n log n)
  3. CΘ(n²)
  4. DΘ(log n)
8.むずかしい

未ソートの配列から k 番目に小さい要素を選択することについて、正しい記述はどれですか？

  1. A選択は O(n²) でしか行えない
  2. Bクイックセレクトはピボットの片側だけで再帰するので、最悪でも O(log n) で動作する
  3. Cクイックセレクトは期待 O(n) で動作し、中央値の中央値法は最悪 O(n) を保証する
  4. D選択にはソートが必要なので、常に Ω(n log n) が必要である

解答

  1. 1. A · 指数的
  2. 2. B · 関数呼び出しの結果を保存し、同じ呼び出しにはメモリから答えること
  3. 3. B · O(log n)
  4. 4. A · O(2ⁿ)
  5. 5. C · 挿入ソートはオーバーヘッドが小さく、小さな入力やほぼソート済みの入力で速いから
  6. 6. C · 指数時間
  7. 7. B · Θ(n log n)
  8. 8. C · クイックセレクトは期待 O(n) で動作し、中央値の中央値法は最悪 O(n) を保証する

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