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

平均実行時間は何を表しますか？

1. A平均的な長さの入力に対する所要時間
2. B最良の場合と最悪の場合の実行時間の中間の値
3. Cサイズ n の入力の与えられた分布に対する期待所要時間
4. D最も一般的なコンピュータでの所要時間

総当たり（brute-force）アルゴリズムとは何ですか？

1. A多数のプロセッサで動作するアルゴリズム
2. B常に再帰を使うアルゴリズム
3. C考えられるすべての候補解を試すアルゴリズム
4. D答えをランダムに推測するアルゴリズム

分割統治アルゴリズムの 3 つのステップは何ですか？

1. A推測、確認、反復
2. B読み込み、計算、書き出し
3. C分割、統治、結合
4. Dソート、探索、返却

多くのライブラリのソート関数が、非常に小さな部分配列では挿入ソートに切り替えるのはなぜですか？

1. A再帰アルゴリズムは 10 要素未満の配列を扱えないから
2. B挿入ソートは最悪の場合 O(n log n) だから
3. C大きな入力では、挿入ソートは他のどのソートアルゴリズムよりメモリが少なくて済むから
4. D挿入ソートはオーバーヘッドが小さく、小さな入力やほぼソート済みの入力で速いから

for i = 1 to n: (j = 1; while j < n: j = j × 2) の時間計算量は何ですか？

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

標準的な 3 重ループで 2 つの n × n 行列を掛ける時間計算量は何ですか？

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

決定問題 X が NP 完全であることを証明するには、どの 2 つのことを示さなければなりませんか？

1. AX に多項式アルゴリズムがないこと、および X が決定可能であること
2. BX が P に属すること、および X が SAT に帰着すること
3. CX が NP に属すること、および既知の NP 完全問題が多項式時間で X に帰着すること
4. DX が P の問題に帰着すること、および X が NP に属すること

一部の辺の重みが負のとき、ダイクストラ法が誤った結果を出すことがあるのはなぜですか？

1. A頂点は取り出された時点で確定するが、後の負の辺によってより短い経路が得られる可能性があるから
2. B負の数は優先度付きキューに格納できないから
3. C無向グラフでしか動作しないから
4. D負の辺があるたびに無限ループに陥るから