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

それぞれ n 回実行される二重の入れ子ループを持つアルゴリズムの計算量は、通常どれですか？

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

平均実行時間は何を表しますか？

1. A最も一般的なコンピュータでの所要時間
2. B最良の場合と最悪の場合の実行時間の中間の値
3. Cサイズ n の入力の与えられた分布に対する期待所要時間
4. D平均的な長さの入力に対する所要時間

0 から k の範囲の n 個の整数に対する計数ソート（counting sort）の実行時間は何ですか？

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

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

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

ある関数は n 回反復するループを 1 つ実行し、その後別に n 回反復するループをもう 1 つ実行します。時間計算量は何ですか？

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

素朴な再帰によるフィボナッチ（fib(n) = fib(n−1) + fib(n−2)）の時間計算量はどれですか？

1. A定数時間
2. B指数時間
3. C線形時間
4. D対数時間

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

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

どんな入力に対してもクイックソートの期待（expected）実行時間を O(n log n) にする手法はどれですか？

1. A常に先頭の要素を選ぶ
2. Bピボットを一様ランダムに選ぶ
3. Cクイックソートを実行する前に入力をソートする
4. D左側にのみ再帰を使う