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

すでにソート済みの配列に対する挿入ソートの最良時間計算量は何ですか？

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

あるループは i = 1 から始まり、i > n となるまで各反復で i を 2 倍にします。何回反復しますか？

1. A約 log₂ n 回
2. B約 n² 回
3. C約 n / 2 回
4. D約 n 回

ある O(n) アルゴリズムは n = 100 万で 3 秒かかります。n = 200 万ではおよそ何秒かかりますか？

1. A12 秒
2. B6 秒
3. C9 秒
4. D3 秒

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

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

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

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

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

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

log(n!) について正しい評価はどれですか？

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

シュトラッセンのアルゴリズムは、半分のサイズのブロックの再帰的な掛け算を 8 回ではなく 7 回にして行列を掛けます。実行時間は何ですか？

1. AΘ(n^{log₂ 7})、約 n^2.81
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n² log n)