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

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

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

増加の下界（lower bound）を表す記法はどれですか？

1. Ao（little o）
2. BO（Big O）
3. CΩ（Big Omega）
4. DΘ（Big Theta）

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

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

比較に基づくソートの最悪の場合の下界はどれですか？

1. AΩ(n)
2. BΩ(n log n)
3. CΩ(n²)
4. DΩ(log n)

満杯になると容量を2倍にする動的配列に要素を追加する操作の償却（amortised）時間計算量は何ですか？

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

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

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

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

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

新しい問題 X が NP 困難であることを示すには、何をしなければなりませんか？

1. AX を多項式時間で検証できることを示す
2. BX を多項式時間で既知の NP 困難な問題に帰着させる
3. C既知の NP 困難な問題を多項式時間で X に帰着させる
4. DX には小さな入力に対する多項式アルゴリズムがないことを示す