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

アルゴリズムとは何ですか？

1. A問題を解く、明確に定義された手順の有限の列
2. Bグラフィカルなインターフェースをもつあらゆるコンピュータプログラム
3. C数式を書くために設計されたプログラミング言語
4. D数値を格納するデータ構造

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

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

隣接リストで格納されたグラフに対する深さ優先探索の時間計算量は何ですか？

1. AO(V + E)
2. BO(V × E)
3. CO(E log V)
4. DO(V²)

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

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

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

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

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

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

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

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

新しい問題 X が NP 困難であることを示すには、何をしなければなりませんか？

1. A既知の NP 困難な問題を多項式時間で X に帰着させる
2. BX を多項式時間で既知の NP 困難な問題に帰着させる
3. CX を多項式時間で検証できることを示す
4. DX には小さな入力に対する多項式アルゴリズムがないことを示す