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

n が大きいとき、最も速く増加する計算量クラスはどれですか？

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

選択ソート（selection sort）はどのように動作しますか？

1. A配列を半分に分け、それらをマージする
2. B順序が逆になっている隣り合う要素を繰り返し交換する
3. Cシフトによって各要素を成長していくソート済み部分に挿入する
4. D未ソート部分の最小値を繰り返し見つけ、それを先頭に交換する

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

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

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

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

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

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

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

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

最短単純路は多項式時間で見つけられます。一般のグラフで 2 頂点間の最長単純路を見つけることについて、何が知られていますか？

1. A重みの符号を反転すればダイクストラ法で解ける
2. BNP 困難である
3. C常に O(V + E) で解ける
4. D決定不能である

2²ⁿ は O(2ⁿ) に属しますか？

1. Aいいえ。2²ⁿ = 4ⁿ であり、4ⁿ / 2ⁿ = 2ⁿ は限りなく大きくなるから
2. Bいいえ。2²ⁿ は 2ⁿ よりゆっくり増加するから
3. Cはい。Big O では指数の定数倍は常に無視されるから
4. Dはい。どちらも指数的だから