線形時間 O(n) — すべての要素を一度処理
O(n)線形時間計算量を理解します。線形検索、カウンティングソート、配列走査などの例を含め、アルゴリズムがすべての要素を調べる必要がある場合を学びます。
Complexity Classes
詳細な説明
O(n)線形時間とは？
アルゴリズムがO(n)とは、実行する作業が入力サイズに直接比例して増加することを意味します。
O(n)が最適である理由
多くの問題には情報理論的下界がO(n)であり、すべての要素を調べずには解決できません。
一般的なO(n)アルゴリズム
| アルゴリズム | 説明 |
|---|---|
| 線形検索 | 各要素を順番にスキャン |
| カウンティングソート | 出現回数をカウント（範囲kが小さい場合） |
| ツーポインタ法 | ソート済み配列で合計がターゲットになるペアを検索 |
| Kadaneのアルゴリズム | 1パスで最大部分配列和 |
シングルパス vs マルチパス
データを2回パスするアルゴリズムもO(n)です — 具体的にはO(2n)ですが、Big-O記法では定数係数は無視されます。
ユースケース
データ処理パイプライン、ETLジョブ、ストリーム処理、データセットのすべてのレコードを検査または変換する必要があるあらゆるシナリオの基盤です。