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

ソート済み配列に対する二分探索（binary search）の時間計算量は何ですか？

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

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

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

ある問題が通常「扱いやすい（tractable）」と呼ばれるのはどのような場合ですか？

1. Aあらゆる可能性を試すことでしか解けない場合
2. B解がない場合
3. C定数時間で解ける場合
4. D多項式時間で解ける場合

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

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

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

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

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

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

停止問題（halting problem）が示していることはどれですか？

1. Aループは避けるべきである
2. Bすべてのプログラムはいずれ停止する
3. Cすべてのプログラムと入力について、それが停止するかどうかを判定できるアルゴリズムは存在しない
4. D一部のプログラムは高速なコンピュータでより速く動作するので、停止するかどうかはハードウェアに依存するから

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

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