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

標準的な配列ベースのマージソートは、どれだけの追加メモリを使いますか？

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

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

1. ABig Theta
2. BBig O
3. CBig Omega
4. DLittle omega

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

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

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

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

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

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

比較に基づくソートの最悪の場合の下界はどれですか？

1. AΩ(log n)
2. BΩ(n²)
3. CΩ(n log n)
4. DΩ(n)

最後の 2 つの値だけを保持するループで n 番目のフィボナッチ数を計算する時間と領域のコストは何ですか？

1. A時間 O(2ⁿ)、領域 O(1)
2. B時間 O(log n)、領域 O(n)
3. C時間 O(n)、領域 O(1)
4. D時間 O(n)、領域 O(n)

ヘルド－カープの動的計画法アルゴリズムは巡回セールスマン問題を厳密に解きます。n 都市に対する実行時間は何ですか？

1. AO(2^n²)
2. BO(n!)
3. CO(n³)
4. DO(n² 2ⁿ)