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

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

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

配列の要素にインデックスでアクセスするのにかかる時間は次のどれですか？

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

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

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

安定（stable）なソートアルゴリズムはどれですか？

1. Aヒープソート
2. Bマージソート
3. C選択ソート（一般的な版）
4. Dクイックソート（一般的なインプレース版）

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

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

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

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

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

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

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

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