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

ある操作が O(1) 時間で動作するとはどういう意味ですか？

1. A実行時間 1 秒あたりちょうど 1 要素を処理する
2. B一度しか実行できない
3. C実行時間が入力サイズとともに増加しない
4. D常にちょうど 1 秒かかる

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

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

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

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

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

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

動的計画法がマージソートを実質的に高速化しないのはなぜですか？

1. A動的計画法はグラフ問題にしか使えず、配列には使えないから
2. Bマージソートはすでに O(n) だから
3. C部分問題が重複しないので、再利用するものがないから
4. Dマージソートには再帰的な構造がないから

k 進数で d 桁の n 個の整数に対する LSD 基数ソートの実行時間は何ですか？

1. AO(n²)
2. BO(n log n)
3. CO(dn log k)
4. DO(d(n + k))

ヘルド－カープの動的計画法アルゴリズムは巡回セールスマン問題を厳密に解きます。n 都市に対する実行時間は何ですか？

1. AO(2^n²)
2. BO(n!)
3. CO(n² 2ⁿ)
4. DO(n³)

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

1. A2ⁿ は n! より速く増加する
2. Bn! は O(n²) である
3. Cn! は 2ⁿ より速く増加する
4. D同じ速さで増加する