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

アルゴリズムの最悪実行時間は何を表しますか？

1. A最小の入力に対する所要時間
2. Bサイズ n のすべての入力にわたる最大の所要時間
3. Cサイズ n のランダムな入力に対する期待所要時間
4. D遅いコンピュータでの所要時間

それぞれ n 回実行される二重の入れ子ループを持つアルゴリズムの計算量は、通常どれですか？

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

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

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

単純な再帰の階乗関数 fact(n) = n × fact(n − 1) はどれだけのスタック領域を使いますか？

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

到達可能な基底部をもたない再帰関数について、正しい記述はどれですか？

1. A自動的に 0 を返す
2. Bコールスタックがオーバーフローするまで自分自身を呼び続ける
3. Cコンパイラが常にそれを、安全に終了するループに変換する
4. DO(1) 時間で動作する

ソート済み配列で、両端から 1 つずつポインタを内側へ動かして、和が目標値になる 2 つの要素を探します。時間計算量は何ですか？

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

ナップサック問題のどの変種で、「重さあたりの価値の順に品物をとる」という貪欲な規則が常に最適解を与えますか？

1. A品物を分割できる分数ナップサック問題
2. Bどちらの変種でもない
3. C品物を必ず丸ごととらなければならない 0/1 ナップサック問題
4. D両方の変種

カラツバ乗算は T(n) = 3T(n/2) + O(n) を満たします。この解は何ですか？

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