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

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

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

再帰とは何ですか？

1. A決して終わらないループ
2. Bソートの手法の一つ
3. Cより小さな入力に対して自分自身を呼び出す関数
4. Dデータ構造の一種

ある問題が通常「扱いやすい（tractable）」と呼ばれるのはどのような場合ですか？

1. A多項式時間で解ける場合
2. Bあらゆる可能性を試すことでしか解けない場合
3. C解がない場合
4. D定数時間で解ける場合

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

1. AO(log n)
2. BO(n)
3. CO(n²)
4. DO(n log n)

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

1. AO(n)
2. BO(2ⁿ)
3. CO(n²)
4. DO(log n)

あるクイックソートは常に最初の要素をピボットに使います。どの入力で最悪の振る舞いを示しますか？

1. Aランダムな順序の配列
2. B長さ 2 の配列
3. Cすでにソートされている配列
4. Dすべての要素が異なる配列

極大マッチングのすべての辺の両端点をとると頂点被覆が得られます。この被覆はどれくらいよいですか？

1. A最適解と比べた品質は不明
2. B最小頂点被覆のサイズの高々 2 倍
3. C最小値の高々 log n 倍
4. D常に最小頂点被覆

シュトラッセンのアルゴリズムは、半分のサイズのブロックの再帰的な掛け算を 8 回ではなく 7 回にして行列を掛けます。実行時間は何ですか？

1. AΘ(n^{log₂ 7})、約 n^2.81
2. BΘ(n²)
3. CΘ(n² log n)
4. DΘ(n³)