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

n 個の数からなる未ソートの配列で最大値を見つける時間計算量は何ですか？

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

選択ソート（selection sort）はどのように動作しますか？

1. A順序が逆になっている隣り合う要素を繰り返し交換する
2. B配列を半分に分け、それらをマージする
3. C未ソート部分の最小値を繰り返し見つけ、それを先頭に交換する
4. Dシフトによって各要素を成長していくソート済み部分に挿入する

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

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

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

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

ボトムアップの表を使って n 番目のフィボナッチ数を計算する時間計算量は何ですか？

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

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

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

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

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

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

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