線形時間

ファイル:Landau notation.svg

横軸に入力長（作業対象）nをとり、縦軸で作業時間を表したグラフ。
オレンジ色の線が、線形時間（O(n)）のアルゴリズムを示し、n（横軸）の増加に比例して作業時間（縦軸）が増加する。
赤色の線はO(n^a)、緑色の線はO(n^b)のアルゴリズムを表している（ただし、b < 1 < a）。

線形時間（せんけいじかん、英: Linear time）は、計算複雑性理論において、入力長 n に対してアルゴリズムの実行時間が線形（O(n)）になるものをいう。例えば、入力された数値列の総和を計算する手続きは数値列の長さに比例した時間を要する。

以上の説明はあまり正確ではなく、実際の実行時間は（特に n が小さい場合）入力長に正確に比例するとは言えない。技術的には十分に大きな n について、アルゴリズムの実行時間が an から bn の範囲にあるとき（a と b は正の定数）、線形時間であるという。詳しくはO記法を参照されたい。

線形時間のアルゴリズムは好ましいものとされることが多い。ほぼ線形時間のアルゴリズムやもっと良いアルゴリズムを見つけようとする研究が盛んに行われてきた。それらの研究にはソフトウェア的手法だけでなくハードウェア的手法も含まれる。ハードウェアの場合、標準的な計算モデルでは線形時間を達成できないアルゴリズムも線形時間にすることが可能な場合がある。例えば、問題の並列性を応用したハードウェア技術などがあり、連想メモリがその1つである。

例えばソートアルゴリズムは、入力となる要素列によっては線形時間でソートを完了するものもあるが、要素同士の比較に基づいたソートアルゴリズムでは一般に O(n log n) より時間を短縮できない。このような複雑性の下限の証明はΩ記法の対象であり、一般的ソートアルゴリズムは Ω(n log n) と言える。同様に無作為な要素列から最大値を探す選択アルゴリズムは、最大値を求めるのに少なくとも (n - 1) 回の比較が必要であることが論理的に示され、Ω(n) となる。

入力全体を見ないと結果が得られない問題は、入力を全て読み込むだけでも線形時間かかるため、少なくとも線形時間以上かかる。

関連項目

• 多項式時間
• 指数関数時間
• 定数時間