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

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

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

配列の要素にインデックスでアクセスするのにかかる時間は次のどれですか？

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

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

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

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

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

単純な再帰の階乗関数 fact(n) = n × fact(n − 1) はどれだけのスタック領域を使いますか？

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

O(n²) のアルゴリズムは O(n³) でもあると言うのは正しいですか？

1. Aはい。Big O は上界であり、n² は n³ より速く増加しないから
2. Bはい。ただし n が 100 より小さい場合に限る
3. Cいいえ。n が大きいとき n³ は n² より小さいから
4. Dいいえ。Big O は常に関数の正確な増加率を述べなければならないから

シュトラッセンのアルゴリズムは、半分のサイズのブロックの再帰的な掛け算を 8 回ではなく 7 回にして行列を掛けます。実行時間は何ですか？

1. AΘ(n²)
2. BΘ(n^{log₂ 7})、約 n^2.81
3. CΘ(n² log n)
4. DΘ(n³)

ヘルド－カープの動的計画法アルゴリズムは巡回セールスマン問題を厳密に解きます。n 都市に対する実行時間は何ですか？

1. AO(2^n²)
2. BO(n³)
3. CO(n² 2ⁿ)
4. DO(n!)