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

マージソートの最悪時間計算量は何ですか？

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

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

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

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

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

問題が最適部分構造をもつとはどういう意味ですか？

1. Aすべての部分問題が同じサイズである
2. B問題の最適解がちょうど 1 つで、すべての部分問題がそれを共有しているから
3. C最適解を部分問題の最適解から構成できる
4. D問題を定数時間で解ける

ある関数は n 回反復するループを 1 つ実行し、その後別に n 回反復するループをもう 1 つ実行します。時間計算量は何ですか？

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

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

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

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

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

どんな入力に対してもクイックソートの期待（expected）実行時間を O(n log n) にする手法はどれですか？

1. A左側にのみ再帰を使う
2. B常に先頭の要素を選ぶ
3. Cクイックソートを実行する前に入力をソートする
4. Dピボットを一様ランダムに選ぶ