線形探索（せんけいたんさく、）は、検索のアルゴリズムの一つ。リストや配列に入ったデータに対する検索を行うにあたって、先頭から順に比較を行い、それが見つかれば終了する。formula_1個のデータからformula_2個のデータを検索する場合、時間計算量はformula_3、空間計算量はformula_4必要となる。下のような7個のデータを持つリストがある。このときに今要素1がどこにあるか、検索したい。線形探索では、最悪のケースは、このリストの場合、要素3を見つけるときで、7個のデータ全てを見ないと、見つけることができない。つまり、n個のデータから1個のデータを検索する場合に最悪formula_5の計算時間を要することとなる。

出典:wikipedia