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

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

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

総当たり（brute-force）アルゴリズムとは何ですか？

1. A常に再帰を使うアルゴリズム
2. B考えられるすべての候補解を試すアルゴリズム
3. C多数のプロセッサで動作するアルゴリズム
4. D答えをランダムに推測するアルゴリズム

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

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

プリム法は最小全域木をどのように構築しますか？

1. A閉路がなくなるまで最も高い辺を取り除く
2. B開始頂点から 1 本の木を成長させ、木から出る最も安い辺を加える
3. Cすべての辺を重みでソートし、森の中で閉路をつくる場合を除いて 1 本ずつ加える
4. D幅優先探索を実行し、BFS 木を残す

辺の重みが非負のグラフで、一つの始点からの最短経路を求めるアルゴリズムはどれですか？

1. ADijkstra 法
2. BKruskal 法
3. Cどの場合でも Bellman–Ford が必要
4. D深さ優先探索（DFS）

あるクイックソートは常に最初の要素をピボットに使います。どの入力で最悪の振る舞いを示しますか？

1. Aすでにソートされている配列
2. Bランダムな順序の配列
3. Cすべての要素が異なる配列
4. D長さ 2 の配列

クラス NP の定義として正しいものはどれですか？

1. Aどのアルゴリズムでも解けない問題
2. B証拠（certificate）が与えられれば、「はい」の答えを多項式時間で検証できる決定問題
3. C多項式でない問題
4. D多項式時間で解けない問題

単方向連結リストでは、二分探索が O(log n) 時間にならないのはなぜですか？

1. A二分探索には少なくとも 2 倍のメモリが必要だから
2. B連結リストのノードでの比較は遅いから
3. Cインデックスによる直接アクセスがないので、中央の要素に到達するのに O(n) ステップかかるから
4. D連結リストはソートできないから