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

空間計算量（space complexity）が測るものはどれですか？

1. Aコードの行数
2. Bコンパイル後のプログラムファイルのディスク容量
3. C入力が大きくなるにつれてアルゴリズムが必要とするメモリ量
4. Dコンピュータの物理的な大きさ

それぞれ n 回実行される二重の入れ子ループを持つアルゴリズムの計算量は、通常どれですか？

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

ある O(n²) アルゴリズムは n = 1000 で 1 秒かかります。n = 2000 ではおよそ何秒かかりますか？

1. A2 秒
2. B4 秒
3. C8 秒
4. D1 秒

クイックソートの最悪時間計算量は何ですか？

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

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

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

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

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

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

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

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

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