LoginSignup
7

More than 5 years have passed since last update.

O記法についてメモ

Last updated at Posted at 2017-07-21

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頁.

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
7