テクノロジ系出題頻度 1/3
線形探索
せんけいたんさく
定義
データを先頭から1つずつ順に調べて目的の値を見つける探索アルゴリズム。
詳細解説
リニアサーチとも呼び、データが整列されていなくても適用できる最も単純な探索手法。計算量は最悪・平均ともにO(n)で、n要素なら平均n/2回の比較が必要。実装が簡単でデータ量が少ない場合や整列されていない場合に有効。データが整列済みなら二分探索の方が高速。試験では二分探索との計算量比較が頻出論点。
「線形探索」が出る問題
関連用語
よくある質問
Q. 線形探索とは何ですか？
A. データを先頭から1つずつ順に調べて目的の値を見つける探索アルゴリズム。
Q. IT パスポート試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 1/3 （★1）。 出題頻度は低めですが、周辺知識として理解しておきましょう。