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

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

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

順序が誤っている隣接要素を繰り返し交換するソートアルゴリズムはどれですか？

1. Aクイックソート（Quicksort）
2. Bヒープソート（Heap sort）
3. Cバブルソート（Bubble sort）
4. Dマージソート（Merge sort）

f(n) = Θ(g(n)) はどういう意味ですか？

1. Aすべての n について f は常に g より小さいので、g は上からは抑えるが下からは決して抑えない
2. Bf は g より真に遅く増加する
3. Cf は g と同じ速さで増加し、上下から g の定数倍で抑えられる
4. Df は g より真に速く増加する

for i = 1 to n: for j = 1 to i: do O(1) work の時間計算量は何ですか？

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

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

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

ある関数は n 回反復するループを 1 つ実行し、その後別に n 回反復するループをもう 1 つ実行します。時間計算量は何ですか？

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

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

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

閉路を作らない最も安い辺を繰り返し追加して最小全域木を求めるアルゴリズムはどれですか？

1. ADijkstra 法
2. B一つのノードから始める Prim 法
3. CFloyd–Warshall
4. DKruskal 法