線形時間

線形時間とは、計算複雑性理論において、アルゴリズムの実行時間が入力サイズnに正比例する（O(n)）状態を指します。これは、入力データが増えるにつれて、計算時間がほぼ直線的に増加することを意味します。例えば、数値列の合計を計算するアルゴリズムは、その数値列の長さに比例した時間を要するため、線形時間アルゴリズムの一例と見なせます。

ただし、実際の実行時間は、特にnが小さい場合には入力サイズに正確に比例するとは限りません。厳密には、十分に大きなnについて、アルゴリズムの実行時間がanからbnの範囲に収まる場合（ここでaとbは正の定数）に線形時間と定義されます。より詳細な解析には、O記法が用いられます。

線形時間のアルゴリズムは、効率的なアルゴリズムとして一般的に好まれます。そのため、線形時間に近いアルゴリズムや、より効率的なアルゴリズムを求める研究が盛んに行われています。これらの研究には、ソフトウェア的なアプローチだけでなく、ハードウェア的なアプローチも含まれます。例えば、ハードウェアでは、並列処理などの技術を利用することで、標準的な計算モデルでは線形時間を達成できないアルゴリズムも線形時間で実行できる可能性があります。連想メモリはその一例です。

一方で、すべての問題に対して線形時間アルゴリズムが存在するわけではありません。例えば、ソートアルゴリズムの中には、特定の入力に対して線形時間で完了するものも存在しますが、要素同士の比較に基づいたソートアルゴリズムでは、一般的にO(n log n)以上の時間がかかります。この複雑さの下限はΩ記法で表され、一般的なソートアルゴリズムはΩ(n log n)となります。同様に、無作為な要素列から最大値を探索する選択アルゴリズムは、少なくともn-1回の比較が必要であり、Ω(n)となります。

入力全体を処理しなければ結果が得られない問題は、少なくとも入力全体を読み込むだけでも線形時間を要します。したがって、このような問題のアルゴリズムは、少なくとも線形時間以上の計算時間を必要とします。線形時間アルゴリズムの効率性は、実際のアプリケーションにおいて非常に重要であり、アルゴリズムの選択や設計において考慮すべき重要な要素です。

関連事項

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

もう一度検索