O(n)おーえぬ

$O\left(N\right)$ は、入力にゅうりょくサイズ $N$ に比例ひれいして計算けいさん量りょうが増ふえるオーダで、線形せんけい時間じかんと呼よばれます。データが 2 倍ばいになれば処理しょり時間じかんも約やく 2 倍ばいになる、素直すなおな増ふえ方かたです。

データ数すう N	おおよその処理しょり量りょう
100	100
1,000	1,000
10,000	10,000

線形探索せんけいたんさく（先頭せんとうから順じゅんに探さがす）・配列はいれつの総和そうわ・最大さいだい値ち検索けんさくなどが代表だいひょう例れいです。たとえば名簿めいぼを 1 件けんずつ全部ぜんぶ見みて条件じょうけんに合あう人ひとを数かぞえる処理しょりは、人数にんずうに比例ひれいした時間じかんがかかるので $O\left(N\right)$ です。多おおくの場面ばめんで「十分じゅうぶん実用じつよう的てき」とされ、$O\left(N^2\right)$ のアルゴリズムを $O\left(N\right)$ に改善かいぜんするのが最適さいてき化かの典型てんけい例れいです。

試験しけんでは $O\left(N\right)$ と $O(\log N)$・$O\left(N^2\right)$ の増ふえ方かたの違ちがい（線形せんけい/対数たいすう/2 乗じょう）を比くらべる問題もんだいが出でます。