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

再帰とは何ですか？

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

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

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

配列の要素にインデックスでアクセスするのにかかる時間は次のどれですか？

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

安定（stable）なソートアルゴリズムはどれですか？

1. Aクイックソート（一般的なインプレース版）
2. B選択ソート（一般的な版）
3. Cヒープソート
4. Dマージソート

for i = 1 to n: for j = 1 to i: do O(1) work の時間計算量は何ですか？

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

活動選択問題で、重ならない活動の数を常に最大にする貪欲な規則はどれですか？

1. A最も早く終わる活動を選び、両立する活動で繰り返す
2. B最も早く始まる活動を選ぶ
3. C重なりの最も少ない活動を先に選び、両立する活動で繰り返す
4. D最も短い活動から選ぶ

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

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

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

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