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

ある O(n) アルゴリズムは n = 100 万で 3 秒かかります。n = 200 万ではおよそ何秒かかりますか？

1. A9 秒
2. B12 秒
3. C3 秒
4. D6 秒

0 から k の範囲の n 個の整数に対する計数ソート（counting sort）の実行時間は何ですか？

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

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

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

k 進数で d 桁の n 個の整数に対する LSD 基数ソートの実行時間は何ですか？

1. AO(dn log k)
2. BO(n²)
3. CO(n log n)
4. DO(d(n + k))

あるクイックソートは常に最初の要素をピボットに使います。どの入力で最悪の振る舞いを示しますか？

1. Aランダムな順序の配列
2. Bすでにソートされている配列
3. Cすべての要素が異なる配列
4. D長さ 2 の配列

O(log n) のように、Big O で対数の底が通常省略されるのはなぜですか？

1. A底は n が小さいときにしか問題にならないから
2. B計算機科学のすべての対数は底が 10 なので、省略されているから
3. C対数は常に整数に丸められるから
4. D底の異なる対数は定数倍しか違わないから

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

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

問題が NP 完全（NP-complete）であるのは、次のどの場合ですか？

1. A停止問題のように、NP に属さないがすべての NP 問題より難しい
2. B多項式時間で解ける
3. C解くことが不可能である
4. DNP に属し、すべての NP 問題が多項式時間でその問題に帰着できる