ランダウの記号のソースを表示

[[File:Mplwp factorial stirling loglog.svg|thumb|300px|[[スターリングの公式]]はランダウの記号を用いて<math>\ln n! = n\ln n - n + O(\ln n)</math>と書くこともできる。]]
'''ランダウの記号'''（ランダウのきごう、{{lang-en-short|Landau symbol}}）は、主に[[関数の極限]]における漸近的な挙動を比較するときに用いられる記法である。英語圏では一般的にビッグ・オー（[[:en:Big_O_notation|Big ''O'']]）と呼ばれる。

'''ランダウの漸近記法''' {{lang|en|(asymptotic notation)}}、'''ランダウ記法''' {{lang|en|(Landau notation)}} あるいは主要な記号として ''O'' （数字の0ではない）を用いることから（バッハマン-ランダウの）''O''-'''記法''' {{lang|en|(Bachmann-Landau O-notation{{sfn|de Bruijn|1981|p={{google books quote|id=7-wxAwAAQBAJ|page=3|3}}}})}}などともいう。

記号 ''O'' は[[ドイツ語]]の{{lang|de|Ordnung}}の[[頭字]]にちなむ<ref name=":0">{{Cite journal|last=Hardy|first=G. H.|last2=Littlewood|first2=J. E.|date=1914|title=Some problems of diophantine approximation: Part II. The trigonometrical series associated with the elliptic ϑ-functions|url=http://projecteuclid.org/euclid.acta/1485887376|journal=Acta Mathematica|volume=37|issue=0|pages=193–239|language=en|doi=10.1007/BF02401834|issn=0001-5962}}</ref>。

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

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

== 概要 ==

ランダウの記号

:<math>f(x)=O(g(x))</math>

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

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

:<math>3x^2 + 4x +10 = O(x^2)</math>

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

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

一方、ランダウの記号

:<math>f(x)=o(g(x))</math>

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

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

:<math>3x^2 + 4x + 10 = o(x^3)</math>

と表すことができる。（ただし、''o''-記法よりも ''O''-記法の方が多くの場合好ましいと考えられている{{sfn|Graham|Knuth|Patashnik|1994|pages=448f}}{{sfn|de Bruijn|1981|page={{google books quote|id=7-wxAwAAQBAJ|page=10|10}}}}。）

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

:<math>f(x)=O(g(x)) \quad (x\to\infty)</math>

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

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

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

を表す。（厳密には[[イプシロン-デルタ論法|ε-δ論法]]で定義する。）特に ''f''(''x'') = ''o''(1) は lim ''f''(''x'') = 0 と同値である。

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

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

と書き表せる。

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

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

== 厳密な定義 ==

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

:<math>f(x)=O(g(x)) \quad (x\to\infty)</math>

を

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

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


また、''a'' を実数とするとき、''a''の[[近傍 (位相空間論)|近傍]]で定義された実数値関数''f''(''x'') と ''g''(''x'') に対し、

:<math>f(x) = O(g(x)) \quad (x \to a)</math>

を

: <math>{}^\exists \delta>0, {}^\exists M>0 \quad \text{ s.t. }\quad {}^\forall x\;[0<|x-a|<\delta \Rightarrow |f(x)|\leq M|g(x)|]</math>

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


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

: <math>\varlimsup_{x\to a} \left|\frac{f(x)}{g(x)}\right| < \infty</math>

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

== 記法の問題 ==

上で定義された

:<math>f(x)=O(g(x))</math> 

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

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

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

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

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

: <math>f \in O(g)</math>

ないし、

: <math>f(x) \le O(g(x))</math>

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

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

:<math>\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}</math>

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

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

例えば三つの目の式は、

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

事を意味する。

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

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

事を意味する。

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

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

== その他の漸近記法 ==

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

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

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

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

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


{| class="wikitable"
|-
! 記法
! 意味
! インフォーマルな定義
! 形式的定義
|-
|<math>f(n) \in O(g(n))</math><br /><math>f(n) = O(g(n))</math><br /><math>f(n) \preceq g(n)</math><br /><math>f(n) \ll g(n)</math>
| <math>f</math> は漸近的に（定数倍を除いて）<math>g</math> によって上からおさえられる
|ある正数 ''k'' に対して、十分大きい ''n'' で <math>|f(n)|  \leq  k\cdot g(n)</math>
|<math>\exists k>0 \; \exists n_0 \; \forall n>n_0 \; |f(n)| \leq k\cdot |g(n)|</math> <br> or <br> <math>  \exists k>0 \; \exists n_0 \; \forall n>n_0 \; f(n) \leq k\cdot g(n)</math>
|-
|<math>f(n) \in \Omega(g(n))</math><br /><math>f(n) = \Omega(g(n))</math><br /><math>f(n) \succeq g(n)</math><br /><math>f(n) \gg g(n)</math>
|'''2つの定義：'''

HLの定義：

<math>f</math> は漸近的に <math>g</math> によって支配されない

今日の定義：

<math>f</math> は漸近的に <math>g</math> によって下からおさえられる
|HLの定義：

無限に多くの ''n'' の値とある正数 ''k'' に対して <math>|f(n)|  \geq  k\cdot g(n)</math>

今日の定義：

ある正数 ''k'' に対して、十分大きい ''n'' で <math>|f(n)|  \geq  k\cdot g(n)</math>

|HLの定義：

<math>\exists k>0 \; \forall n_0 \; \exists n>n_0 \; f(n) \geq k\cdot g(n)</math>

今日の定義：

<math>\exists k>0 \; \exists n_0 \; \forall n>n_0 \; f(n) \geq k\cdot g(n)</math>
|-
|<math>f(n) \in \Theta(g(n))</math><br /><math>f(n) = \Theta(g(n))</math><br /><math>f(n) \asymp g(n)</math>
| <math>f</math> は漸近的に <math>g</math> によって上と下両方からおさえられる
|ある正数 ''k''<sub>1</sub>, ''k''<sub>2</sub> に対して、十分大きい ''n'' で <math>k_1\cdot g(n) \leq |f(n)| \leq k_2\cdot g(n)</math>
|<math>\exists k_1>0 \; \exists k_2>0 \; \exists n_0 \; \forall n>n_0</math>
<math>k_1\cdot g(n) \leq f(n) \leq k_2\cdot g(n)</math>
|-
|<math>f(n) \in o(g(n))</math><br /><math>f(n) = o(g(n))</math><br /><math>f(n) \prec g(n)</math>
| <math>f</math> は漸近的に <math>g</math> によって支配される
| 任意の正数 <math>k</math> を固定するごとに、十分大きい ''n'' を取ると <math>|f(n)| \le k\cdot|g(n)|</math>
|<math>\forall k>0 \; \exists n_0 \; \forall n>n_0 \; |f(n)| \le k\cdot |g(n)|</math>
|-
|<math>f(n) \in \omega(g(n))</math><br /><math>f(n) = \omega(g(n))</math><br /><math>f(n) \succ g(n)</math>
| <math>f</math> は漸近的に <math>g</math> を支配する
|任意の正数 <math>k</math> を固定するごとに、十分大きい ''n'' を取ると <math>|f(n)| \ge k\cdot|g(n)|</math>
|<math>\forall k>0 \; \exists n_0 \; \forall n>n_0 \  |f(n)| \ge k\cdot |g(n)|</math>
|-
|<math>f(n)\sim g(n)\!</math>
| <math>f</math> は漸近的に <math>g</math> に等しい
|<math>f(n)/g(n) \to 1</math>
|<math>\forall \varepsilon>0\;\exists n_0\;\forall n>n_0\;\left|{f(n) \over g(n)}-1\right|<\varepsilon</math>
|}

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

を

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

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

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

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

''o''-記法は[[微分]]の定義や、極めて一般の空間における微分可能性を定義するのに有効である。また、関数の漸近同値を
: <math> f\sim g \iff (f-g) = o(g) </math>
と定めることができる。これは[[同値関係]]であり、上述の ''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'' はおよそ log<sub>2</sub> ''N'' なので、例えば「多項式時間」といったとき、これは''N'' の多項式ではなく ''n'' の多項式を表す。

{| class="wikitable" style="background-color:white;"
! 記法 !! 名称!! アルゴリズムの例
|-
|<math>O\left(1\right)</math>|| [[定数時間]] (Constant time) || （整数の）偶奇判別
|-
|<math>O\left(\log^* n\right)</math> || [[反復対数]] (iterated logarithmic) || Hopcroft, Ullmanによる[[素集合データ構造]]における探索アルゴリズム
|-
|<math>O\left(\log n\right)</math>|| [[対数]] (logarithmic) || ソート済み配列における[[二分探索]]
<!--|-
|<math>O\left(\left(\log n\right)^c\right), \exist c>0</math> || 対数[[多項式]] (polylogarithmic) ||[[AKS素数判定法]]による自然数''n''の素数判定（''n''は入力サイズではない）★通常はビット長で計算量評価をするので不適切-->
|-
|<math>O\left({n^c}\right), 0< \exist c<1</math>|| 分数指数関数 (fractional power) || [[kd木]]上の探索 
|-
|<math>O\left(n\right)</math>|| [[線形関数]] (linear) || 非ソート配列上の探索、[[離散ウェーブレット変換]]
|-
|<math>O\left(n\log n\right)</math> || 準線形、線形対数 (linearithmic, loglinear, or quasilinear) || [[ヒープソート]]、[[高速フーリエ変換]]
|-
|<math>O\left({n^2}\right)</math> || 二乗時間 (quadratic) || [[挿入ソート]]、[[離散フーリエ変換]]
|-
|<math>O\left({n^c}\right), \exist c\ge 1</math>|| [[多項式時間]] (polynomial)  || [[ワーシャル-フロイド法]]
|-
|<math>O{(2^n)}</math> || 指数時間 ([[:en:Time_complexity#Exponential_time|exponential]], geometricとも) || （現在最も速い）[[巡回セールスマン問題]]の（厳密解の）解法
|-
|<math>O\left(n!\right)</math> || [[階乗]]関数 (factorial, combinatorialとも) || 2つの[[論理式 (数学)|論理式]]の同型判定[http://citeseer.ist.psu.edu/588414.html]、巡回セールスマン問題の（可能）解の枚挙
|-
|<math>O\left(2^{c^n}\right) \exist c>0 </math> || 二重指数時間 || AC[[ユニフィケーション|単一化子]]の完備集合の探索[http://citeseer.ist.psu.edu/337363.html]
|}

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

== 歴史 ==

''O''-記法はドイツの数論家である[[:en:Paul Bachmann|ポール・バッハマン]]によって1894年に彼の著書『解析数論』(''{{lang|de|Analytische Zahlentheorie}}''<ref>[https://archive.org/stream/dieanalytischeza00bachuoft#page/401/mode/1up インターネット・アーカイブ].</ref>) の第二巻で初めて導入された（1892年に著された第一巻では用いられていない）。これに触発されて[[エドムント・ランダウ]]が1909年に''o''-記法を発明した{{sfn|Graham|Knuth|Patashnik|1994|page=448}}。

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

また{{仮リンク|イヴァン・ヴィノグラードフ|label=ヴィノグラードフ|en|Ivan Vinogradov}}は <math> f = O(g) </math> と <math> f \ll g </math> を同じ意味で用いている<ref>{{cite book
|author=I. M. Vinogradov
|title=The Method of Trigonometrical Sums in the Theory of Numbers
|year=2004
|publisher=Dover
|isbn=0-486-43878-3
|url={{google books|sEaS79bAPGcC|plainurl=yes}}
|page=ix
}}</ref>{{sfn|Knuth|1976}}。

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

== 具体例 ==

{{内容過剰|date=2016年1月}}

関数 ''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>より速く発散する関数は'''超多項式''' {{lang|en|(''superpolynomial'')}} と呼ばれる。また、どのような定数 ''c'' に対しても ''c''<sup>''n''</sup> よりも遅く発散する関数は'''準指数関数''' {{lang|en|(''subexponential'')}} と呼ばれる。アルゴリズムの計算量が超多項式かつ準指数関数であることもあり得る。例えば、現在知られている内で最も早い[[因数分解]]のアルゴリズムもこれに含まれる。

''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> に支配されることを表現する。

== 脚注 ==
{{reflist}}

== 参考文献 ==
* {{cite book
|和書
|year      = 2007
|title     = 岩波 数学辞典
|edition   = 第4版
|editor    = [[日本数学会]]
|publisher = [[岩波書店]]
|isbn      = 978-4-00-080309-0
|ref        = {{sfnref|岩波数学辞典|2007}}
}}
* {{cite book
    |last1              = de Bruijn
    |first1             = N. G.
    |year               = 1981
    |title              = Asymptotic Methods in Analysis
    |url                = {{google books|7-wxAwAAQBAJ|plainurl=yes}}
    |publisher          = Dover
    |isbn               = 0-486-64221-6
    |mr                 = 
    |zbl                = 0556.41021
    |ref                = harv
}}
* {{cite book
|last1=Graham
|first1=R. L.
|author2=Knuth
|first2=D. E.
|author3=Patashnik
|first3=O.
|title=Concrete Mathematics
|edition=Second
|year=1994
|publisher=Addison-Wesley
|isbn=0-201-55802-5
|ref=harv
}}
* Marian Slodicka & Sandy Van Wontergem. ''Mathematical Analysis I''. University of Ghent, 2004.
* {{cite magazine|author=Donald Knuth|author-link=ドナルド・クヌース|title=Big Omicron and big Omega and big Theta|date=Apr.–June 1976|periodical=ACM SIGACT News|volume=8|issue=2|pages=18–24|url=http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron.pdf|doi=10.1145/1008328.1008329|ref={{sfnref|Knuth|1976}}}}
* 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.
* {{cite book|author = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | id = ISBN 0-534-94728-X}} Pages 226–228 of section 7.1: Measuring complexity.
* Jeremy Avigad, Kevin Donnelly. ''[http://www.andrew.cmu.edu/~avigad/Papers/bigo.pdf 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.

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

{{DEFAULTSORT:らんたうのきこう}}
[[Category:数学の表記法]]
[[Category:アルゴリズム解析]]
[[Category:計算複雑性理論]]
[[Category:漸近解析]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]