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

挿入ソート（insertion sort）の最悪時間計算量は何ですか？

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

アルゴリズムの最悪実行時間は何を表しますか？

1. A遅いコンピュータでの所要時間
2. Bサイズ n のランダムな入力に対する期待所要時間
3. Cサイズ n のすべての入力にわたる最大の所要時間
4. D最小の入力に対する所要時間

ピボットを選び、配列を小さい要素と大きい要素に分割するソートアルゴリズムはどれですか？

1. Aバブルソート
2. Bマージソート
3. Cクイックソート（quicksort）
4. D挿入ソート

長さ m と n の文字列の最長共通部分列を求める標準的な動的計画法の時間計算量は何ですか？

1. AO(m + n)
2. BO(mn)
3. CO(mn log n)
4. DO(2^m+n)

V 個の頂点と E 本の辺をもつグラフに対するベルマン－フォード法の時間計算量は何ですか？

1. AO(V³ × E)
2. BO(V + E)
3. CO(E log V)
4. DO(V × E)

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

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

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

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

最後の 2 つの値だけを保持するループで n 番目のフィボナッチ数を計算する時間と領域のコストは何ですか？

1. A時間 O(2ⁿ)、領域 O(1)
2. B時間 O(n)、領域 O(1)
3. C時間 O(n)、領域 O(n)
4. D時間 O(log n)、領域 O(n)