線形時間
線形時間(せんけいじかん、英: Linear time)は、計算複雑性理論において、入力長 n に対してアルゴリズムの実行時間が線形(O(n))になるものをいう。例えば、入力された数値列の総和を計算する手続きは数値列の長さに比例した時間を要する。
以上の説明はあまり正確ではなく、実際の実行時間は(特に n が小さい場合)入力長に正確に比例するとは言えない。技術的には十分に大きな n について、アルゴリズムの実行時間が an から bn の範囲にあるとき(a と b は正の定数)、線形時間であるという。詳しくはO記法を参照されたい。
線形時間のアルゴリズムは好ましいものとされることが多い。ほぼ線形時間のアルゴリズムやもっと良いアルゴリズムを見つけようとする研究が盛んに行われてきた。それらの研究にはソフトウェア的手法だけでなくハードウェア的手法も含まれる。