【応用情報技術者試験】O(n)（オーダーN）

O(n)（オーダーN）とは、アルゴリズムの計算量がデータ量（n）に比例して増える「線形時間」の計算量オーダーです。データ量が2倍、10倍になれば処理時間も2倍、10倍になるため、1つのループで配列を走査する際などで使われます。主な類語には「線形時間」があります。

走査
対象物を点や線で順次なぞり、画像・信号情報を読み取ったり（入力）、映像を再構成（出力）したりする技術。

詳細な解説

• 意味: データ量 nに対して計算時間が C × n (Cは定数）の比例関係で増加する。
• 特徴: 直感的に理解しやすく、配列の全要素を一度だけ探索する線形探索が典型例です。
• 具体例: 配列の全要素を順番に表示する、リストの合計を計算する、1重のループ処理。
• 類似用語・関連表記:
  • 線形時間: 処理速度の分類。
  • O(1): データ量に関係なく処理時間が一定。
  • O(n log n): マージソートなど、線形より少し重い処理。
  • O(n²): 2重ループなど、データ量の2乗に比例。

O(n)は、アルゴリズムの処理効率を評価する上で、効率的な部類に入る「線形時間」を表す非常に重要な基準となります。