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

n 個の要素を持つ未ソートの配列に対する線形探索（linear search）の時間計算量（最悪の場合）は何ですか？

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

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

1. ALittle omega
2. BBig Theta
3. CBig Omega
4. DBig O

二分探索は入力に何を要求しますか？

1. A配列の要素が 1000 個以下であること
2. B配列が正の数だけを含むこと
3. C配列の長さが 2 のべき乗であること
4. D配列がソートされていること

安定（stable）なソートアルゴリズムはどれですか？

1. A選択ソート（一般的な版）
2. Bクイックソート（一般的なインプレース版）
3. Cマージソート
4. Dヒープソート

多くのライブラリのソート関数が、非常に小さな部分配列では挿入ソートに切り替えるのはなぜですか？

1. A挿入ソートは最悪の場合 O(n log n) だから
2. B挿入ソートはオーバーヘッドが小さく、小さな入力やほぼソート済みの入力で速いから
3. C再帰アルゴリズムは 10 要素未満の配列を扱えないから
4. D大きな入力では、挿入ソートは他のどのソートアルゴリズムよりメモリが少なくて済むから

ソート済み配列で、両端から 1 つずつポインタを内側へ動かして、和が目標値になる 2 つの要素を探します。時間計算量は何ですか？

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

ベルマン－フォード法は、始点から到達可能な負の重みの閉路をどのように検出しますか？

1. Aダイクストラ法を 2 回実行し、2 つの距離の結果を比べる
2. B負の重みをもつ辺があるかどうかを調べる
3. CV − 1 回のラウンドの後、まだ緩和できる辺があるかどうかを調べる
4. D深さ優先探索で閉路を数える

挿入ソートはソート済みの入力に対して O(n) で動作します。これは比較ソートの Ω(n log n) の下界と矛盾しますか？

1. Aはい。ただし 100 より短い配列の場合に限る
2. Bいいえ。下界はすべての入力にわたる最悪の場合に適用されるのであって、すべての入力に適用されるわけではない
3. Cいいえ。挿入ソートは比較ソートではないから
4. Dはい。したがって下界は誤りである