O記法は計算にかかる時間とデータ量の関係について便利な記法
$$O(n)$$
「$n$ のオーダーである」,「オーダーエヌ」,「オーエヌ」,「線形時間」と呼ぶ.
配列への挿入のように「データの量 $n$ が2倍になったら計算時間も2倍くらいになる」という性質
$$O(1)$$
「定数のオーダーである」,「オーダーイチ」,「オーワン」,「定数時間」と呼ぶ.
連結リストへの挿入のように「データの量 $n$ が2倍になろうが計算時間は変わらない」という性質
$$O(n^{2})$$
データ量 $n$ が2倍,3倍になったときに,計算時間が4倍,9倍に増える
$$O(\log n)$$
データ量 $n$ が2倍になったときに増える計算時間と,データ量が2倍から4倍になった時に増える計算時間が同じくらい
O記法は関数の増え方をざっくりと表現するものなので,$n^{2}+2n+1$ であっても $3n^{2}$ であっても,どちらも $O(n^{2})$
厳密な定義の解説はたとえば,奥村晴彦『C言語による最新アルゴリズム事典』 技術評論社,1991年.を参照して欲しい
参考文献
西尾泰和 『コーディングを支える技術 ~成り立ちから学ぶプログラミング作法 (WEB+DB PRESS plus)』 技術評論社,2013年,141頁.