線型探索
線型探索(せんけいたんさく、英: linear search, sequential search)は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。
n {\displaystyle n} 個のデータから m {\displaystyle m} 個のデータを検索する場合、時間計算量は O ( n m ) {\displaystyle O(nm)} 、空間計算量は O ( 1 ) {\displaystyle O(1)} である。
「馬鹿サーチ」とも呼ばれるものの、データ数が少ない場合は優秀なアルゴリズムだと謂える。プログラミング言語の予約語探索などでは、理論的にはハッシュ法のほうが早いが、全体の効率を考えると、あまり影響はない。