ランダウの記号

**ランダウの記号**（ランダウのきごう、）は、主に関数の極限における漸近的な挙動を比較するときに用いられる記法である。英語圏では一般的にビッグ・オー（Big ''O''）と呼ばれる。

**ランダウの漸近記法** 、**ランダウ記法**  あるいは主要な記号として *O* （数字の0ではない）を用いることから（バッハマン-ランダウの）*O*-**記法** などともいう。

記号 *O* はドイツ語のの頭字にちなむ。

なおここでいうランダウはエトムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。

ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。

## 概要

ランダウの記号

:f(x)=O(g(x))

は 、*x* が充分大きいとき関数 *f* が関数 *g* に比例もしくはそれ以下におさえられることを示す。

たとえば二次関数 3*x*2 + 4*x* &plus; 10 が *x* を限りなく大きくしたときどのように増大するかを考えると、変数 *x* が 2 より大きければ第一項 3*x*2 が他の項より大きく、さらに大きくなるほど支配的になることがわかる。漸近解析をする上では定数倍のような詳細は必要としないことが多く、*O*-記法を用いると、必要な情報を

:3x^2 + 4x +10 = O(x^2)

と端的に表すことができる。

このように関数 *g* としては関数 *f* よりも単純なもの（上の例では *x*2）が通常用いられる。（#一般的なオーダー参照。）

一方、ランダウの記号

:f(x)=o(g(x))

は関数 *f* がおおよそ関数 *g* 未満であることを示している。

たとえば *x* が十分大きいとき 3*x*2 + 4*x* &plus; 10 は *x*3 と比べると小さくなり、*o*-記法を用いると、これを

:3x^2 + 4x + 10 = o(x^3)

と表すことができる。（ただし、*o*-記法よりも *O*-記法の方が多くの場合好ましいと考えられている。）

これまでは変数を限りなく大きくしたときを例に説明してきたが、他にも変数を限りなく小さくしたときや、定数に限りなく近づけたときの漸近挙動も同様にランダウ記法で表すことができる。どの意味で記号が用いられているのかを

:f(x)=O(g(x)) \quad (x\to\infty)

のように明示する書き方もある。

*f*(*x*) = *O*(*g*(*x*)), *f*(*x*) = *o*(*g*(*x*)) (*x* → ∞) はそれぞれ

*\lim_{x\to\infty} \left|\frac{f(x)}{g(x)}\right| 　が存在する場合には、その値が有限（0 も含む）であること（一般の場合は後述）。極限が存在しない場合、即ち振動する場合でも該当することはあることには注意されたい。
*\lim_{x\to\infty} \left| \frac{f(x)}{g(x)} \right| =0

を表す。（厳密にはε-δ論法で定義する。）特に *f*(*x*) = *o*(1) は lim *f*(*x*) = 0 と同値である。

ランダウ記法は様々な分野で有益であり、たとえば指数関数を3次までテイラー展開したものは

: \mathrm{e}^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+O(x^4)\quad (x\to 0)

と書き表せる。

記号 *O* と*o* は通常、関数の収束や発散の漸近的な上界を記述する為に用いられる。同様に漸近的な下界を記述する為にΩ, ωという類似記法が用いられ、上下両方を記述する為にΘ という記法を用いる。

ただし、Ω、ω、Θは主に計算機科学で用いられる記法であり、数学では *O* と *o* をこれらの意味に流用する事が多い（どの意味で用いているのかは文脈から判断）。

## 厳密な定義

十分大きい全ての実数 *x* に対し定義されている実数値関数 *f*(*x*) と *g*(*x*) に対し、

:f(x)=O(g(x)) \quad (x\to\infty)

を

: {}^\exists x_0, {}^\exists M>0 \quad \text{ s.t. }\quad{}^\forall x \; [x>x_0 \Rightarrow |f(x)|\leq M|g(x)|]

と定義し、「*f*(*x*) が *x* &rarr; &infin; のとき オーダー*O*(*g*(*x*)) である」と呼ぶ。

また、*a* を実数とするとき、*a*の近傍で定義された実数値関数*f*(*x*) と *g*(*x*) に対し、

:f(x) = O(g(x)) \quad (x \to a)

を

: {}^\exists \delta>0, {}^\exists M>0 \quad \text{ s.t. }\quad {}^\forall x\;[0

で定義し、「*f*(*x*) が *x* &rarr; *a* のとき オーダー*O*(*g*(*x*)) である」と呼ぶ。

なお、*a* の十分近くで　*g*(*x*) が 0 を値にとらない場合、f(x)=O(g(x))は

: \varlimsup_{x\to a} \left|\frac{f(x)}{g(x)}\right| 

が満たされることと同値である（*a* が∞の場合も同様）。特に *f*(*x*) = *O*(1) は、近傍において *f*(*x*) が有界であることと同値である。

## 記法の問題

上で定義された

:f(x)=O(g(x)) 

という記法は広く用いられている確立した慣習ではあるが紛らわしい記法の濫用で、二つの関数が等しいという意味ではない。

この記法の濫用は、等号の両辺に*O* -記法が登場した際に問題となり、例えば*x* →∞のとき、

: 　O(x) = O(x^2) 　であるが、　O(x^2)\ne O(x)　である。

すなわち、両辺に*O* -記法が登場した場合には、直観的には十分大きな*x* で左辺/右辺が定数未満になる事を意味する。

こうした記法上の問題を回避する為に、

: f \in O(g)

ないし、

: f(x) \le O(g(x))

と書く流儀もあるが、一般的ではない。前者の場合、「*O*(*g*)」 は *g* の定数倍によって押さえられる関数全体からなる集合であるとみなしていることになる。

より複雑な使い方としては、*O*( ) が等式の異なる場所に複数、もちろん両辺にわたって複数回現れるというものがある。例えば、以下は *n* &rarr; &infin; で正しい内容を記述している。

:\begin{align}&(n+1)^2 = n^2 + O(n),\\ &(n+O(n^{1/2}))(n + O(\log\,n))^2 = n^3 + O(n^{5/2}),\\ & n^{O(1)} = O(e^n).\end{align}

これらの式の意味は、次のように解釈する：

: 左辺の *O*() を満たす「任意の」関数に対して、右辺の *O*() を満たす「ある」関数を適切に選べば、それらの関数を代入した等式の両辺が等しいようにできる。

例えば三つの目の式は、

: 任意の関数 *f*(*n*) = *O*(1) に対し、*g*(*n*) = *O*(*e**n*) を満たす*g*を適切に選べばn^{f(n)} \le g(n)が成立する

事を意味する。

二つの目の式のように左辺に複数の*O*()がある場合は、それらすべてに対して上述のルールを適用する。したがって二つの目の式は、

: 任意の関数f_1(n) = O(n^{1/2})\, 、f_2(n) = O(O(\log\,n))\, に対し、g(n) = O(n^{5/2})\, を満たす*g*を適切に選べば(n+f_1(n))(n + f_2(n))^2 \le n^3 + g(n)が成立する

事を意味する。

## 性質
*O*-記法は次の性質を満たす。*o*-記法も同様の性質を満たす。
; 推移律 :  f(n) = O(g(n)),\ g(n) = O(h(n)) \implies f(n) = O(h(n)). 
; 和 :  O(f(n)) + O(f(n)) = O(f(n)). 
; 積 :  O(f(n)) O(g(n)) = O(f(n)g(n)), \qquad f(n) O(g(n)) = O(f(n)g(n)). 
; 定数倍 :  O(cf(n)) = O(f(n)) \quad (c \neq 0). 
; 冪等性 :  O(O(f(n))) = O(f(n)). 
また *p*(*n*) と *q*(*n*) をゼロでない *n* の多項式とすると
:\begin{align}
&p(n) = O(q(n)) & &\iff & &\deg p(n) \le \deg q(n)\\
&p(n) = o(q(n)) & &\iff & &\deg p(n) 
が成り立つ。

## 多変数の場合
漸近記法は多変数になっても有効である。たとえば
: f(n,m) = n^2 + m^3 + O(n+m) \quad(\mbox{as } n,m\to\infty)
という言及が示唆するのは、定数 *C*, *N* で
: \forall n, m>N: |g(n,m)| \le C(n+m)
を満たすものの存在である。ここで *g*(*n*, *m*) は
: f(n,m) = n^2 + m^3 + g(n,m)
で定められるものである。混乱を避けるためには、動かす変数は常に明示する必要がある。つまり
: f(n,m) = O(n^m) \quad (\mbox{as } n,m\to\infty)
という言明は、次の
: \forall m: f(n,m) = O(n^m) \quad (\mbox{as } n\to\infty)
とは明確に異なる言明である。

## その他の漸近記法

*O*-記法と関連がある、Ω-記法、ω-記法、Θ-記法を導入する。

Ω-記法とω-記法はそれぞれ、*O*-記法と*o*-記法の定義で大小を反転させる事により得られる。Θ-記法Θ(g)は *O(g)* と Ω*(g)* を両方満たすことを意味する。

ただし、Ω-記法に関しては、この記法を初めて導入したハーディーとリトルウッドは今日のそれとは若干異なった意味に用いていたので、あわせてそれも記す。(以下の表の「HLの定義」の部分)。

今日の定義との違いの要点をかいつまんでいえば、今日の定義ではΩ-記法は前述のように*O*-記法の定義の大小反転だが、ハーディー達の定義ではΩ(g)は*o(g)*を満たさない事として定義していた。

両者の定義は性質のよい関数、例えば多項式に対しては同値だが、極限に近づく際に振動するような関数に関しては必ずしも同値ではない。

また、計算機科学では
: f(n) = \tilde{O} (g(n))

を

: \exists k \quad \text{ s.t. }\quad  f(n) = O(g(n) \log^k(g(n)))

の意味で用いる。対数因子を無視すればこれは本質的には O-記法である。この記法は "nit-picking" のクラスを記述するのにしばしば用いられる。これは log*k*(*n*) が任意の定数 *k* と正の定数 &epsilon; に対して常にo(*n*&epsilon;) となるからである。

## 一般化と関連用法
関数のとりうる値は、絶対値をノルムに取り替えるだけでそのまま任意のノルム線型空間の元に一般化できる。*f* や *g* は同じ空間に値を取る必要はない。*g* のとる値は任意の位相群の元にすることも可能である。

「極限操作」"*x* &rarr; *x*0" は、勝手なフィルター基の導入によって *f* と *g* の有向点族として一般化される。

*o*-記法は微分の定義や、極めて一般の空間における微分可能性を定義するのに有効である。また、関数の漸近同値を
:  f\sim g \iff (f-g) = o(g) 
と定めることができる。これは同値関係であり、上述の *f* が &Theta;(*g*) 程度であるという関係よりもなお強い制限を表す記法になっている。*f* と *g* が正値実数値関数なら lim *f*/*g* = 1 なる関係式に簡略化できる。例えば、2*x* は &Theta;(*x*) のオーダーだが、 2*x* &minus; *x* は *o*(*x*) のオーダーでない。

## 一般的なオーダー

計算機科学、特に計算量理論、アルゴリズム論、暗号理論では、アルゴリズムの計算時間を評価するのに *O*-記法を頻繁に用いる。

アルゴリズムの計算量の評価よく使われる*O*-記法関数の種類を示す。

これらの中でも特に重要なものには、個別の名称がついている(多項式時間など)。

以下、 *n*はアルゴリズムに入力されるデータのビット数を表す。

注意しなければならないのは、アルゴリズムに整数 *N* を入力するときである。*N* のビット数 *n* はおよそ log2 *N* なので、例えば「多項式時間」といったとき、これは*N* の多項式ではなく *n* の多項式を表す。

一般的ではないが、更に発散速度の速い関数も存在する（アッカーマン関数 A(*m, n*) など）。逆に更に発散速度の遅い関数として、逆関数である逆アッカーマン関数 α(*n*) などもあり、実際にあるアルゴリズムの計算量の見積りとして出現する。この関数は上界こそないものの、非常に発散速度が遅いために実用的には定数と見なされる (α(3) = 1, α(7) = 2, α(61) = 3, \alpha(2^{2^{2^{65536}}} - 3) = 4, ...)。

## 歴史

*O*-記法はドイツの数論家であるポール・バッハマンによって1894年に彼の著書『解析数論』(**') の第二巻で初めて導入された（1892年に著された第一巻では用いられていない）。これに触発されて[[エドムント・ランダウ]]が1909年に''o''-記法を発明した。

なお、[[ゴッドフレイ・ハロルド・ハーディ|ハーディ]]と[[ジョン・エデンサー・リトルウッド|リトルウッド]]もランダウの記号<math> f=O(g)\, </math>に相当するものを別の記号<math> f\preceq g\, </math>で表現している。彼らはΩ-記法も現在と近い意味で用いており、今日の言葉でいえば、彼らのΩはo(g)でない事を表している。

または <math> f = O(g) </math> と <math> f \ll g </math> を同じ意味で用いている。

[[ドナルド・クヌース]]は、計算機科学の世界に''O''-記法を導入し、Ω-記法やΘ-記法も再導入した。

== 具体例 ==



関数 ''f''(''n'') が他の関数の有限和で表せるとき(多項式であるとき)、その内最も発散速度の速い関数が ''f''(''n'') のオーダーを決定づける。以下にその例を挙げる。
: <math>f(n) = 9 \log n + 5 (\log n)^3 + 3n^2 + 2n^3 \in O(n^3).</math>

例での場合、係数を無視して''n''に関する項を見ると、log ''n''、(log ''n'')<sup>''3''</sup>、''n''<sup>''2''</sup>、''n''<sup>''3''</sup>の4つが存在し、このうち''n''<sup>''3''</sup>が最も発散が速い。そのため、他の''n''に関する項に関わらず、オーダーは''O''(''n''<sup>''3''</sup>)とする。

特に、関数が ''n'' の多項式でおさえられるならば、''n'' が無限大に発散するに従ってより低いオーダーの項まで無視できるようになる。

''O''(''n''<sup>''c''</sup>) と ''O''(''c''<sup>''n''</sup>) は全く異なる。前者の定数 ''c''がどれほど大きかろうと、後者の方がずっとずっと速く発散する。どのような定数 ''c'' に対しても ''n''<sup>''c''</sup>より速く発散する関数は**超多項式**  と呼ばれる。また、どのような定数 ''c'' に対しても ''c''<sup>''n''</sup> よりも遅く発散する関数は**準指数関数*'  と呼ばれる。アルゴリズムの計算量が超多項式かつ準指数関数であることもあり得る。例えば、現在知られている内で最も早い[[因数分解]]のアルゴリズムもこれに含まれる。

*O*(log&thinsp;*n*) と *O*(log(*n*<sup>*c*</sup>)) は全く等価である。なぜならば、log(*n*<sup>*c*</sup>) = *c* log&thinsp;*n* より2つの指数関数は定数係数のみが異なり、これは big *O*-記法では無視されるからである。同様に異なる底を持つ対数関数も等価であるが、一方、異なる底を持つ指数関数は等価ではない。これはよくある勘違いである。例えば、2<sup>*n*</sup> と 3<sup>*n*</sup> は同じオーダーではない。

入力サイズの単位の変更は、アルゴリズムの計算量を変えるかもしれないしそうでないかもしれない。単位を変更するということは、関数に現れる全ての *n* にある定数を掛けることと同じである。例えば、アルゴリズムが *n*<sup>2</sup> のオーダーで動くとき、*n* を *cn* で置き換えれば計算量は *c*<sup>2</sup>*n*<sup>2</sup> となり、big *O*-記法では *c*<sup>2</sup> は無視されるので計算量は変化しない (*c*<sup>2</sup>*n*<sup>2</sup> &isin; *O*(*n*<sup>2</sup>))。しかし例えば 2<sup>*n*</sup> のオーダーで動くアルゴリズムでは、*n* を *cn* で置き換えると計算量は 2<sup>*cn*</sup> = (2<sup>*c*</sup>)<sup>*n*</sup> となる。これは 2<sup>*n*</sup> とは等しくない（もちろん、*c* = 1 の場合を除く）。

=== 例 === 
次の多項式関数を考える

: <math>\begin{align} f(x) & = 6x^4 -2x^3 +5, \\ g(x) & = x^4.\end{align}</math>

このとき、*f*(*x*) のオーダーは *O*(*g*(*x*)) または *O*(*x*<sup>4</sup>) である。実際、オーダーの定義からこれはある定数 *C*と *x*<sub>0</sub> が存在して、*x*<sub>0</sub> &lt;  *x* なる任意の *x* に対し &#x007c;*f*(*x*)&#x007c; &le; *C* &#x007c;*g*(*x*)&#x007c; が成り立つことを意味するが、*x* &gt; 1 において
: <math>\begin{align} |6x^4 - 2x^3 + 5| 
 & \le 6x^4 + 2x^3 + 5\\ & \le 6x^4 + 2x^4 + 5x^4\\ & \le 13x^4\\ & \le 13 |x^4|
\end{align}</math>
であるから、*C* = 13, *x*<sub>0</sub> = 1 とおけばよい。

*[[リーマン予想]]が正しければ、*x* 以下の[[素数]]の個数 &pi;(*x*) は次のように<div style="margin:1ex auto 1ex 3em;"><math>\pi(x) = \int_2^x\frac{dt}{\log t} + O(\sqrt{x}\,\log x)</math></div>と評価できる（[[素数定理]]も参照）。
*[[バブルソート]]の時間的計算量を考えると、*n* 個の要素からなる列をソートするのに掛かる時間は*O*(*n*<sup>2</sup>) である。[[クイックソート]]を使えば、平均計算時間を *O*(*n* log&thinsp;*n*) に改善できる（但し最悪時には*O*(*n*<sup>2</sup>)）。
* *n* 次[[正方行列]]の[[固有値]]を求めるアルゴリズムは、少なくともその行列に含まれる *n*<sup>2</sup> 個の要素を読み取らなければならない。従って、固有値を求めるアルゴリズムの時間的計算量の下界は &Omega;(*n*<sup>2</sup>) である。
すなわち、一般的な行列に対してその固有値を計算するのに掛かる時間が *n*<sup>2</sup> のオーダーを下回るアルゴリズムは存在しない。

=== 無限大における漸近挙動と計算量の見積り ===
*O*-記法はアルゴリズムの効率を解析するのに有用である。たとえば、あるサイズ *n* の問題(例えば処理すべきデータが *n* 個あるなど)を解くのに掛かる時間あるいは手順数が *T*(*n*) = 4*n*<sup>2</sup> &minus; 2*n* + 2 である場合を考える。

このとき、*n* を次第に大きくしていくと、 *T*(*n*) に対して *n*<sup>2</sup> の項の影響が支配的になり、他の項はほとんど無視できるようになる（たとえば *n* = 500 としてみると、4*n*<sup>2</sup> の項は 2*n* の項の実に1000倍であり、後者を無視しても式に与える影響は、計算量を考える上でほとんど無視できる）。

さらに、*n*<sup>3</sup> や 2<sup>*n*</sup> といった他のオーダーの式と比較する分には係数も無関係になる（たとえば *T*(*n*) = 1,000,000*n*<sup>2</sup> のように係数が大きい関数と、それより指数が1大きい *U*(*n*) = *n*<sup>3</sup> を比較する。仮に *n* = 1,000,000 としてみると *T*(1,000,000) = 1,000,000×1,000,000<sup>2</sup> = 1,000,000<sup>3</sup> = *U*(1,000,000) だから、*n* > 1,000,000 の場合は常に *U*(*n*) > *T*(*n*) である。）。

こうして残る影響をすくい上げて、*O*-記法では
: <math>T(n)\in O(n^2)</math>
と書いて、「*n*<sup>2</sup> のオーダーである」と言い、これによってこのアルゴリズムの時間あるいは手順数*T*(*n*) の増加具合が *n*<sup>2</sup> に支配されることを表現する。

== 脚注 ==


== 参考文献 ==
* 
* 
* 
* Marian Slodicka & Sandy Van Wontergem. *Mathematical Analysis I*. University of Ghent, 2004.
* 
* Donald Knuth. *The Art of Computer Programming*, Volume 1: *Fundamental Algorithms*, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 1.2.11: Asymptotic Representations, pp.107&ndash;123.
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[ロナルド・リベスト|Ronald L. Rivest]], and [[Clifford Stein]]. *Introduction to Algorithms*, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 3.1: Asymptotic notation, pp.41–50.
*  Pages 226–228 of section 7.1: Measuring complexity.
* Jeremy Avigad, Kevin Donnelly. *Formalizing O notation in Isabelle/HOL*
* Paul E. Black,  [http://www.nist.gov/dads/HTML/bigOnotation.html "big-O notation"], in *Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 11 March 2005. Retrieved December 16, 2006.
* Paul E. Black, [http://www.nist.gov/dads/HTML/littleOnotation.html "little-o notation"], in *Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.
* Paul E. Black, [http://www.nist.gov/dads/HTML/omegaCapital.html "Ω"], in *Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.
* Paul E. Black, [http://www.nist.gov/dads/HTML/omega.html "ω"], in *Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 29 November 2004. Retrieved December 16, 2006.
* Paul E. Black, [http://www.nist.gov/dads/HTML/theta.html "Θ"], in *Dictionary of Algorithms and Data Structures'' [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.

## 関連項目
* 漸近展開 - テーラーの公式の一般化である関数の近似
* 漸近最適 - 考えている問題の下界となる定数の範囲内に上界が漸近的に収まるようなアルゴリズムを記述する際にしばしば用いられる用語
* ハーディー記法 - 別の漸近記法
*  - 有界な複素解析関数について、積分変換の収束域について述べるためのもの