基本情報技術者試験 練習問題 11：計算量（時間計算量と空間計算量）
アルゴリズムの計算量について述べた文として、正しいものはどれか。
- 線形探索の時間計算量はO(log n)であり、バイナリサーチより高速である。
- バイナリサーチ（二分探索）は検索対象がソート済みである必要があり、時間計算量はO(log n)である。
- マージソートの時間計算量はO(n log n)であり、クイックソートより常に高速である。
- ハッシュテーブルは衝突回避が不可能なため、検索時間が常にO(n)である。
- 計算量が小さいアルゴリズムは必ず実行時間が短く、常に優れたアルゴリズムである。
Qraftユーザーの成績：難易度 Dランク（レーティング1132）・正答率 63%（10/16回正解）
レーティングは解いた人の実力と正誤から算出する難しさ（初期値1200）。ランクはその全問題中の順位（S+が最難関、F-が最易）
正解と解説を見る
正解：バイナリサーチ（二分探索）は検索対象がソート済みである必要があり、時間計算量はO(log n)である。
アルゴリズムの効率を評価する際に、計算量（特に時間計算量）の理解は重要です。
線形探索（Linear Search）：
- ソート済みでない配列から要素を順番に探索します。
- 時間計算量：O(n)（最悪の場合、n回の比較が必要）
バイナリサーチ（Binary Search）：
- ソート済みの配列に対して、探索範囲を半分に絞りながら探索します。
- 時間計算量：O(log n)（非常に高速）
- 前提条件：配列がソート済みであること
正しいのは「バイナリサーチ（二分探索）は検索対象がソート済みである必要があり、時間計算量はO(log n)である」です。
ソートアルゴリズム：
- マージソート：時間計算量O(n log n)で、常に安定（同値要素の相対順序を保持）
- クイックソート：平均時間計算量O(n log n)だが、最悪O(n^2)。実装によっては高速。
- 常に同じ計算量で動作するわけではありません。
ハッシュテーブル：
- 理想的な場合は検索時間O(1)ですが、ハッシュ衝突時はO(n)になる可能性があります。
- 優れたハッシュ関数と衝突解決戦略により、平均O(1)を実現します。
計算量が小さいアルゴリズムでも、実装の複雑さやメモリアクセスパターンにより、実際の実行時間は異なります。