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

再帰とは何ですか？

1. Aソートの手法の一つ
2. B決して終わらないループ
3. Cデータ構造の一種
4. Dより小さな入力に対して自分自身を呼び出す関数

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

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

ある操作が O(1) 時間で動作するとはどういう意味ですか？

1. A実行時間が入力サイズとともに増加しない
2. B一度しか実行できない
3. C実行時間 1 秒あたりちょうど 1 要素を処理する
4. D常にちょうど 1 秒かかる

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

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

O(log n) のように、Big O で対数の底が通常省略されるのはなぜですか？

1. A底の異なる対数は定数倍しか違わないから
2. B対数は常に整数に丸められるから
3. C計算機科学のすべての対数は底が 10 なので、省略されているから
4. D底は n が小さいときにしか問題にならないから

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

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

little-o 記法について正しい記述はどれですか？

1. Aどの関数も自分自身の little-o なので、n = o(n)
2. B2n はゆっくり増加するので、2n = o(n)
3. Cn = o(n²) だが、n は o(n) ではない
4. Dn² = o(n)

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

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