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

アルゴリズムとは何ですか？

1. A数式を書くために設計されたプログラミング言語
2. Bグラフィカルなインターフェースをもつあらゆるコンピュータプログラム
3. C数値を格納するデータ構造
4. D問題を解く、明確に定義された手順の有限の列

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

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

分割統治アルゴリズムの 3 つのステップは何ですか？

1. A読み込み、計算、書き出し
2. B分割、統治、結合
3. C推測、確認、反復
4. Dソート、探索、返却

標準的な 3 重ループで 2 つの n × n 行列を掛ける時間計算量は何ですか？

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

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

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

1,000,000 要素のソート済み配列に対して、二分探索は最悪の場合およそ何回の比較を必要としますか？

1. A約 20 回
2. B約 500,000 回
3. C約 1,000 回
4. D約 100 回

n 個の未ソート要素からボトムアップ法で二分ヒープを構築する時間計算量は何ですか？

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

マスター定理を用いると、T(n) = 8T(n/2) + O(n²) の解はどれですか？

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