ビッグオー記法​

ビッグオー記法は、定義域における関数のおおよその大きさを記述する数学表記法である。ビッグオー記法は、ドイツの数学者パウル・バッハマン[1]とエドムンド・ランダウ[2]によって考案され、後に他の人々によって拡張された一連の記法の一つであり、総称し^{てバッハマン・}ランダウ記法^{と呼ばれる} 。文字Oは、近似の順序を意味するOrdnungを表すためにバッハマンによって選ばれた。

コンピュータサイエンスでは、ビッグオー表記法は、入力サイズが大きくなるにつれて実行時間やメモリ要件 ^{[ a ]}がどのように大きくなるかによってアルゴリズムを分類するために使用されます。 ^{[ 3 ]}解析数論 では、ビッグオー表記法は算術関数の増加に対する境界を表現するためによく使用されます。よく知られた例の 1 つは素数定理の剰余項です。^{[ 4 ]}微積分を含む数学的解析 では、ビッグオー表記法はべき級数を切り捨てるときに誤差を制限したり、実数値または複素数値関数をより単純な関数で近似する品質を表現するために使用されます。

多くの場合、ビッグオー記法は、変数が大きくなるにつれて関数の成長率に基づいて関数を特徴づけます。つまり、同じ漸近的成長率を持つ異なる関数は、同じオー記法で表すことができます。関数の成長率は関数の位数とも呼ばれるため、文字「オー」が使われます。ビッグオー記法による関数の記述は、関数の成長率の 上限のみを示します。

ビッグO表記法に関連して、、、、、、、、、などの記号を使用して成長率の他の種類の境界を記述するいくつかの関連表記^法があり^ます。^[ 5 ^{] [ 6 ] [ 7} ]${\displaystyle o}$ ${\displaystyle \sim}$ ${\displaystyle \オメガ}$ ${\displaystyle \ll}$ ${\displaystyle \gg}$ ${\displaystyle \asymp}$ ${\displaystyle \omega }$ ${\displaystyle \Theta}$

正式な定義

推定対象となる関数を定義域上で定義された実数値または複素数値関数とし、比較関数を同じ集合上で定義された非負の実数値関数とする。定義域の一般的な選択肢としては、有界または非有界の実数区間、正の整数の集合、複素数の集合、実数と複素数の組などがある。定義域を明示的に記述するか暗黙的に理解するかによって、次のように書ける。 ${\textstyle f,}$ ${\textstyle D,}$ ${\textstyle g,}$ ${\textstyle D.}$

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\ }$$

これは、次 の正の実数が存在する場合に 「${\textstyle f(x)}$ はより大きい${\textstyle O}$ 」 と読みます。${\textstyle g(x)}$ ${\textstyle M}$

$${\displaystyle \left|f(x)\right|\leq M\ g(x)\qquad ~{\mathsf {\ for\ all\ }}~\quad x\in D.}$$

（つまり、gも決してゼロにならない）領域全体にわたって、比が有界である、つまり、すべての に対して となる正の実数が存在する、という定義は、コンピュータサイエンスと数学におけるbig のあらゆる用途を網羅しており、領域が有限、無限、実数、複素数、一変数、多変数の場合の使用も含まれます。ほとんどのアプリケーションでは、 の引数に現れる関数は、定数因子と低次の項を省略して、できるだけ単純な形式になるよう選択します。この数は、通常は指定されないため、暗黙の定数と呼ばれます。big 記法を使用する場合、重要なことは、有限が存在するということであり、その特定の値ではありません。これにより、多くの解析不等式の表現が簡素化されます。 ${\displaystyle g(x)>0}$ ${\displaystyle D,}$ ${\textstyle {\frac {f(x)}{g(x)}}}$ ${\displaystyle M}$ ${\textstyle {\Big |}{\frac {f(x)}{g(x)}}{\Big |}\leq M}$ ${\displaystyle x\in D.}$ ${\textstyle O}$ ${\displaystyle g(x)}$ ${\textstyle O{\bigl (}\cdot {\bigr )}}$ ${\textstyle M}$ ${\textstyle O}$ ${\displaystyle M}$

正の実数または正の整数で定義された関数については、より制限的で多少矛盾する定義が、特にコンピュータサイエンスの分野では今でも一般的に使われている^{[ 3 ] [ 8 ]} 。最終的に正になる関数に限定すると、

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\qquad ~{\mathsf {as}}\quad x\to \infty }$$

は、領域内の何らかの実数に対して を意味する。ここで、式 は極限を示すのではなく、が十分に大きい場合に不等式が成り立つという概念を示す。式 は省略されることが多い。^{[ 3 ]}${\textstyle a,}$ ${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$ ${\textstyle \left[a,\infty \right).}$ ${\textstyle x\to \infty }$ ${\textstyle x.}$ ${\textstyle x\to \infty }$

同様に有限実数の場合、 ${\textstyle a,}$

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\qquad ~{\text{ as }}\ x\to a}$$

は、の区間にある定数に対して、 の小さな近傍内であることを意味します 。さらに、表記法は を意味します。より複雑な表現も可能です。 ${\textstyle c>0,}$ ${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$ ${\displaystyle \left[a-c,a+c\right];}$ ${\displaystyle a.}$ $${\displaystyle \ f(x)=h(x)+O{\bigl (}g(x){\bigr )}\ }$$ ${\textstyle f(x)-h(x)=O{\bigl (}g(x){\bigr )}.}$

等号（＝）が書かれているにもかかわらず、この表現は等式ではなく、不等式と関係していることを示しています。${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$ ${\textstyle f}$ ${\textstyle g.}$

1930年代^{[ 6 ]}に、ロシアの数論学者IMヴィノグラドフは、数論^{[ 4 ] [ 9 ] [ 10 ]}やその他の数学の分野でますます使用されるようになった記法を、記法の代替として導入しました。 ${\displaystyle \ll ,}$ ${\textstyle O}$

$${\displaystyle \ f\ll g\iff f=O{\bigl (}g{\bigr )}.}$$

多くの場合、同じ作品で両方の表記法が使われます。

ビッグOのセットバージョン

コンピュータサイエンス^{[ 3 ]}では、 bigを関数の${\textstyle O}$ 集合も定義するものとして定義するのが一般的です。正（または非負）の関数が指定されている場合、bigは、を満たすすべての関数の集合を表すと解釈されます。これは、「関数は、最大で次数のすべての関数の集合に含まれる」と 同等に記述できます。${\displaystyle g(x)}$ ${\textstyle O{\bigl (}g(x){\bigr )}}$ ${\textstyle {\tilde {f}}}$ ${\textstyle {\tilde {f}}(x)=O{\bigl (}g(x){\bigr )}.}$ ${\textstyle f(x)\in O{\bigl (}g(x){\bigr )},}$ ${\textstyle \ f(x)\ }$ ${\textstyle g(x).}$

無限領域の例

典型的な用法では、この表記法は実数の無限区間に適用され、非常に大きな に対する関数の挙動を捉えます。この設定では、「最も急速に」増加する項の寄与が、最終的に他の項を無関係にします。結果として、以下の簡略化規則を適用できます。 ${\displaystyle O}$ ${\displaystyle [a,\infty )}$ ${\displaystyle x}$

• 複数の項の合計である場合、成長率が最も大きい項があればそれを保持し、その他すべてを省略することができます。${\displaystyle f(x)}$
• が複数の因数の積である場合、定数（ に依存しない積の因数）は省略できます。${\displaystyle f(x)}$ ${\displaystyle x}$

例えば、 とし、表記法を使用してこの関数を簡略化し、が大きい場合の成長率を記述するとします。この関数は、、、および の3 つの項の和です。これらの 3 つの項のうち、成長率が最も高い項は、の関数として最大の指数を持つ項、つまり です。ここで 2 番目の規則を適用できます。はとの積であり、最初の因子は に依存しません。この因子を省略すると、簡略化された形式 になります。したがって、は の「ビッグ O」であると言えます。数学的には、すべての に対して と書くことができます。この計算は、正式な定義を使用して確認できます。およびとします。上記の正式な定義を適用すると、 というステートメントは、 適切に選択した正の実数に対して、すべての に対して という展開 と同等です。これを証明するには、 とします。すると、すべての に対して となります。 したがって 、 と同じ議論により、 であることも成り立ちますが 、これは関数 の精度の低い近似です。一方、この文は誤りです。なぜなら、この項は無制限になる から です。${\displaystyle f(x)=6x^{4}-2x^{3}+5}$ ${\displaystyle O}$ ${\displaystyle x}$ ${\displaystyle 6x^{4}}$ ${\displaystyle -2x^{3}}$ ${\displaystyle 5}$ ${\displaystyle x}$ ${\displaystyle 6x^{4}}$ ${\displaystyle 6x^{4}}$ ${\displaystyle 6}$ ${\displaystyle x^{4}}$ ${\displaystyle x}$ ${\displaystyle x^{4}}$ ${\displaystyle f(x)}$ ${\displaystyle x^{4}}$ ${\displaystyle f(x)=O(x^{4})}$ ${\displaystyle x\geq 1}$ ${\displaystyle f(x)=6x^{4}-2x^{3}+5}$ ${\displaystyle g(x)=x^{4}}$ ${\displaystyle f(x)=O(x^{4})}$ $${\displaystyle |f(x)|\leq Mx^{4}}$$ ${\displaystyle M}$ ${\displaystyle x\geq 1}$ ${\displaystyle M=13}$ ${\displaystyle x\geq 1}$ $${\displaystyle {\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|-2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}}$$ $${\displaystyle |6x^{4}-2x^{3}+5|\leq 13x^{4}.}$$ ${\displaystyle f(x)=O(x^{10})}$ ${\displaystyle f}$ ${\displaystyle f(x)=O(x^{3})}$ ${\displaystyle 6x^{4}}$ ${\displaystyle f(x)/x^{3}}$

関数が入力 を持つアルゴリズムに必要なステップ数を記述する場合、暗黙のドメインが正の整数の集合である のような式は 、アルゴリズムの時間計算量が最大で のオーダーであると解釈できます。 ${\displaystyle T(n)}$ ${\displaystyle n}$ $${\displaystyle T(n)=O(n^{2})}$$ ${\displaystyle n^{2}}$

有限領域の例

Big O は、有限区間における数学関数の近似における誤差項を記述するためにも使用できます。最も重要な項は明示的に記述され、最も重要でない項は単一の Big O 項にまとめられます。例えば、指数級数と、が小さい 場合に有効な2つの式を考えてみましょう。 中央の式（「」の行）は、 が小さい場合、誤差の絶対値 が最大で定数倍であることを意味します。これはテイラーの定理の使用例です。 ${\displaystyle x}$ $${\displaystyle {\begin{aligned}e^{x}&=1+x+{\frac {\;x^{2}\ }{2!}}+{\frac {\;x^{3}\ }{3!}}+{\frac {\;x^{4}\ }{4!}}+\dotsb &&{\text{ for all finite }}x\\[4pt]&=1+x+{\frac {\;x^{2}\ }{2}}+O(|x|^{3})&&{\text{ for all }}|x|\leq 1\\[4pt]&=1+x+O(x^{2})&&{\text{ for all }}|x|\leq 1.\end{aligned}}}$$ ${\displaystyle O(|x^{3}|)}$ ${\displaystyle \ e^{x}-(1+x+{\frac {\;x^{2}\ }{2}})\ }$ ${\displaystyle ~|x^{3}|\ }$ ${\displaystyle \ x~}$

与えられた関数の挙動は有限領域と無限領域で大きく異なる可能性がある。例えば 、 $${\displaystyle (x+1)^{8}=x^{8}+O(x^{7})\quad {\text{ for }}x\geq 1}$$ $${\displaystyle (x+1)^{8}=1+8x+O(x^{2})\quad {\text{ for }}|x|\leq 1.}$$

多変量の例

$${\displaystyle x\sin y=O(x)\quad {\text{ for }}x\geq 1,y{\text{ any real number}}}$$

$${\displaystyle 3a^{2}+7ab+2b^{2}+a+3b+14\ll a^{2}+b^{2}\ll a^{2}\quad {\text{ for all }}a\geq b\geq 1}$$

$${\displaystyle {\frac {xy}{x^{2}+y^{2}}}=O(1)\quad {\text{ for all real }}x,y{\text{ that are not both }}0}$$

$${\displaystyle x^{it}=O(1)\quad {\text{ for }}x\neq 0,t\in \mathbb {R} .}$$

ここでは2変数の複素変数関数を扱っています。一般に、有界関数は です。 ${\displaystyle O(1)}$

$${\displaystyle (x+y)^{10}=O(x^{10})\quad {\text{ for }}x\geq 1,-2\leq y\leq 2.}$$

最後の例は、さまざまな変数における有限領域と無限領域の混合を示しています。

これらの例において、境界は両変数において一様です。多変数式では、ある変数が他の変数よりも重要になる場合があり、その場合は、大文字のO記号または記号の添え字を用いて、暗黙の定数が1つ以上の変数に依存することを表現できます。例えば、次の式を考えてみましょう。 ${\displaystyle M}$ ${\displaystyle \ll }$

$${\displaystyle (1+x)^{b}=1+O_{b}(x)\quad {\text{ for }}0\leq x\leq 1,b{\text{ any real number.}}}$$

これは、各実数に対して、 に依存する定数 が存在することを意味します。そのため、すべての に対して、 この特定の記述は一般二項定理に従います。 ${\displaystyle b}$ ${\displaystyle M_{b}}$ ${\displaystyle b}$ ${\displaystyle 0\leq x\leq 1}$ $${\displaystyle |(1+x)^{b}-1|\leq M_{b}\cdot x.}$$

テイラー級数の理論でよく見られる別の例は、次のとおりです。 ここで、暗黙の定数はドメインのサイズに依存します。 $${\displaystyle e^{x}=1+x+O_{r}(x^{2})\quad {\text{ for all }}|x|\leq r,r{\text{ being any real number.}}}$$

下付き文字の規則はこのページの他のすべての表記に適用されます。

プロパティ

製品

${\displaystyle f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})}$

${\displaystyle f\cdot O(g)=O(|f|g)}$

和

ならば。ならば。​​​ ${\displaystyle f_{1}=O(g_{1})}$ ${\displaystyle f_{2}=O(g_{2})}$ ${\displaystyle f_{1}+f_{2}=O(\max(g_{1},g_{2}))}$ ${\displaystyle f_{1}=O(g)}$ ${\displaystyle f_{2}=O(g)}$ ${\displaystyle f_{1}+f_{2}=O(g)}$

定数による乗算

kを非ゼロの定数とします。すると となります。言い換えれば、ならば ${\displaystyle O(|k|\cdot g)=O(g)}$ ${\displaystyle f=O(g)}$ ${\displaystyle k\cdot f=O(g).}$

推移的性質

ならば、。 ​ ${\displaystyle f=O(g)}$ ${\displaystyle g=O(h)}$ ${\displaystyle f=O(h)}$

正の整数の 関数が他の関数の有限和として表せる場合、最も速く増加する関数が の位数を決定します。例えば、 ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle f(n)}$

${\displaystyle f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{for }}n\geq 1.}$

無限への成長に関するいくつかの一般的な規則。以下の 2 番目と 3 番目の特性は、ロピタルの規則を使用して厳密に証明できます。

大国が小国を支配する

の場合、 ${\displaystyle b>a\geq 0}$ $${\displaystyle n^{a}=O(n^{b}).}$$

対数はべき乗が支配的である

任意の正の に対して、 がどれだけ 大きくても がどれだけ小さくても 関係ありません。ここで、暗黙の定数は と の両方に依存します。 ${\displaystyle a,b,}$ $${\displaystyle (\log n)^{a}=O_{a,b}(n^{b}),}$$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$

指数関数は累乗を支配する

どんなに大きくても小さくて も、どんなにポジティブなものでも。 ${\displaystyle a,b,}$ $${\displaystyle n^{a}=O_{a,b}(e^{bn}),}$$ ${\displaystyle a}$ ${\displaystyle b}$

任意の に対してよりも速く増加する関数は、超多項式 と呼ばれます。 の形の任意の指数関数よりも遅く増加する関数は、劣指数関数と呼ばれます。アルゴリズムによっては、超多項式かつ劣指数関数的な時間を必要とする場合があります。このような例としては、整数因数分解の既知の最速アルゴリズムや関数 などがあります。 ${\displaystyle n^{c}}$ ${\displaystyle c}$ ${\displaystyle c^{n}}$ ${\displaystyle c>1}$ ${\displaystyle n^{\log n}}$

対数の内部におけるのべき乗は無視できます。 が正の数である場合、 の表記はと全く同じ意味になります。なぜなら だからです。同様に、異なる定数の底を持つ対数は、Big O表記に関して等価です。一方、異なる底を持つ指数関数は同じ位数ではありません。例えば、と は同じ位数ではありません。 ${\displaystyle n}$ ${\displaystyle c}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log(n^{c}))}$ ${\displaystyle \log(n^{c})=c\log n}$ ${\displaystyle 2^{n}}$ ${\displaystyle 3^{n}}$

より複雑な表現

より複雑な用法では、は方程式の異なる場所に出現し、各辺に複数回出現することもあります。例えば、正の整数について以下が成り立ちます。 これらの文の意味は次のとおりです。左辺でそれぞれ を満たす任意の関数に対して、右辺でそれぞれ を満たす関数 がいくつか存在し、これらの関数すべてを方程式に代入すると両辺が等しくなります。例えば、上記の3番目の方程式は、「 を満たす任意の関数に対して、となる関数が存在する」という意味です。文「 」に含まれる暗黙の定数は、式「 」に含まれる暗黙の定数に依存する場合があります。 ${\displaystyle O(\cdot )}$ ${\displaystyle n}$ $${\displaystyle {\begin{aligned}(n+1)^{2}&=n^{2}+O(n),\\(n+O(n^{1/2}))\cdot (n+O(\log n))^{2}&=n^{3}+O(n^{5/2}),\\n^{O(1)}&=O(e^{n}).\end{aligned}}}$$ ${\displaystyle O(\cdot )}$ ${\displaystyle O(\cdot )}$ ${\displaystyle f(n)=O(1)}$ ${\displaystyle g(n)=O(e^{n})}$ ${\displaystyle n^{f(n)}=g(n)}$ ${\displaystyle g(n)=O(e^{n})}$ ${\displaystyle f(n)=O(1)}$

さらにいくつかの例: $${\displaystyle {\begin{aligned}f=O(g)\;&\Rightarrow \;\int _{a}^{b}f=O{\bigg (}\int _{a}^{b}g{\bigg )}\\f(x)=g(x)+O(1)\;&\Rightarrow \;e^{f(x)}=O(e^{g(x)})\\(1+O(1/x))^{O(x)}&=O(1)\quad {\text{ for }}x>0\\\sin x&=O(|x|)\quad {\text{ for all real }}x.\end{aligned}}}$$

ヴィノグラドフの ≫ とクヌースの大きな Ω

が両方とも正関数であるとき、ヴィノグラドフ^{[ 6 ]}はという表記を導入した。これは と同じ意味である。ヴィノグラドフの2つの表記は視覚的に対称性があり、正関数 については、 ${\displaystyle f,g}$ ${\displaystyle f(x)\gg g(x)}$ ${\displaystyle g(x)=O(f(x))}$ ${\displaystyle f,g}$ $${\displaystyle f(x)\ll g(x)\Longleftrightarrow g(x)\gg f(x).}$$

1976年にドナルド・クヌース^{[ 7 ]} は次のように定義した 。

${\displaystyle f(x)=\Omega (g(x))\Longleftrightarrow g(x)=O(f(x))}$

これは、Vinogradov の と同じ意味です。 ${\displaystyle f(x)\gg g(x)}$

はるか以前、ハーディとリトルウッドは を異なる方法で定義していましたが、これは現在ではほとんど使われていません（イヴィッチの著書^{[ 9 ]}は唯一の例外です）。より強い性質を表すために記号を使用したことを正当化して、クヌースは次のように書いています。 ^{[ 7 ]}「私がこれまでに見てきたコンピュータサイエンスのあらゆる応用において、より強い要件の方がはるかに適切です」。クヌースはさらに、「私はハーディとリトルウッドの の定義を変更しましたが、彼らの定義が広く使われているわけではなく、彼らの定義が適用される比較的まれなケースでは、彼らが言いたいことを他の方法で表現できるため、変更しても正当だと感じています」と書いています。^{[ 7 ]}${\displaystyle \Omega }$ ${\displaystyle \Omega }$ ${\displaystyle \Omega }$

実際、クヌースのビッグは、コンピューターサイエンスと組み合わせ論の一般的な特徴であるため、 ハーディ–リトルウッドのビッグよりもはるかに広く使用されています。${\displaystyle \Omega }$ ${\displaystyle \Omega }$

ハーディの≍とクヌースの大きなΘ

解析的数論において、^{[ 10 ]}という表記はと の両方を意味する 。この表記はもともとハーディによるものである。^{[ 5 ]} クヌースは同じ概念を という表記で表した。^{[ 7 ]}大まかに言えば、これらの文はと が同じ位数を持つことを主張している。これらの表記は、 の共通定義域内の すべての に対して となる 正の定数が存在することを意味する。関数がビッグ O のように正の整数または正の実数で定義されている場合、筆者はしばしば および が十分に大きいすべての に対して、つまりある点 を超えるすべての に対して成り立つと解釈する 。これは、文に を付記することで示されることがある。たとえば、 は 定義域に対して真であるが、定義域がすべて正の整数の場合は で関数が 0 となるため偽である。 ${\displaystyle f(x)\asymp g(x)}$ ${\displaystyle f(x)=O(g(x))}$ ${\displaystyle g(x)=O(f(x))}$ ${\displaystyle f(x)=\Theta (g(x))}$ ${\displaystyle f(x)}$ ${\displaystyle g(x)}$ ${\displaystyle M,N}$ $${\displaystyle Ng(x)\leq f(x)\leq Mg(x)}$$ ${\displaystyle x}$ ${\displaystyle f,g}$ ${\displaystyle f(x)=\Omega (g(x))}$ ${\displaystyle f(x)=\Theta (g(x))}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x_{0}}$ ${\displaystyle x\to \infty }$ $${\displaystyle 2n^{2}-10n=\Theta (n^{2})}$$ ${\displaystyle n\geq 6}$ ${\displaystyle n=5}$

その他の例

$${\displaystyle n^{3}+20n^{2}+n+12\asymp n^{3}\quad {\text{ for all }}n\geq 1.}$$

$${\displaystyle (1+x)^{8}=x^{8}+\Theta (x^{7})\quad {\text{ for all }}x\geq 1.}$$

表記

$${\displaystyle f(n)=e^{\Omega (n)}\quad {\text{ for all }}n\geq 1,}$$ は、すべての に対して となる 正の定数が存在することを意味します。対照的に、 は、 すべての に対して となる 正の定数が存在することを意味します。また、 は、 すべての に対して と なる正の定数が存在することを意味します。 ${\displaystyle M}$ ${\displaystyle f(n)\geq e^{Mn}}$ ${\displaystyle n\geq 1}$ $${\displaystyle f(n)=e^{-O(n)}\quad {\text{ for all }}n\geq 1,}$$ ${\displaystyle M}$ ${\displaystyle f(n)\geq e^{-Mn}}$ ${\displaystyle n\geq 1}$ $${\displaystyle f(n)=e^{\Theta (n)}\quad {\text{ for all }}n\geq 1,}$$ ${\displaystyle M,N}$ ${\displaystyle e^{Mn}\leq f(n)\leq e^{Nn}}$ ${\displaystyle n\geq 1}$

任意のドメイン について、 各文は内のすべての に対して となります。 ${\displaystyle D}$ $${\displaystyle f(x)=g(x)+O(1)\Longleftrightarrow e^{f(x)}\asymp e^{g(x)},}$$ ${\displaystyle x}$ ${\displaystyle D}$

一般的な関数の順序

アルゴリズムの実行時間を分析する際によく遭遇する関数のクラスのリストを以下に示します。いずれの場合も、cは正の定数であり、n は無限に増加します。一般的に、増加速度の遅い関数から順にリストアップされます。

表記	名前	例
${\displaystyle O(1)}$	絶え間ない	ソートされた数値配列の中央値を求める; 計算; 一定サイズのルックアップテーブルを使用する${\displaystyle (-1)^{n}}$
${\displaystyle O(\alpha (n))}$	逆アッカーマン関数	分離集合データ構造における操作ごとの償却複雑度
${\displaystyle O(\log \log n)}$	二重対数	均一に分布した値のソートされた配列内で 補間検索を使用して項目を見つけるのに費やされた比較の平均数
${\displaystyle O(\log n)}$	対数	ソートされた配列内の項目を二分探索またはバランス探索木で探すこと、および二項ヒープ内のすべての操作
${\displaystyle O((\log n)^{c})}$ ${\textstyle c>1}$	多重対数	行列連鎖順序付けは、並列ランダムアクセスマシン上で多重対数時間で解決できます。
${\displaystyle O(n^{c})}$ ${\textstyle 0<c<1}$	分数乗	kdツリーの検索
${\displaystyle O(n)}$	リニア	ソートされていないリストまたはソートされていない配列内の項目の検索。リップルキャリーによる2つのnビット整数の加算。
${\displaystyle O(n\log ^{*}n)}$	nログスターn	ザイデルのアルゴリズム[ 11 ]を使用して単純な多角形の三角測量を実行すると、${\displaystyle \log ^{*}(n)={\begin{cases}0,&{\text{if }}n\leq 1\\1+\log ^{*}(\log n),&{\text{if }}n>1\end{cases}}}$
${\displaystyle O(n\log n)=O(\log n!)}$	線形、対数線形、準線形、または「」${\displaystyle n\log n}$	高速フーリエ変換の実行、可能な限り最速の比較ソート、ヒープソートとマージソート
${\displaystyle O(n^{2})}$	二次関数	教科書的な掛け算で2桁の数字を掛け算する。バブル ソート、選択ソート、挿入ソートなどの単純なソート アルゴリズム。クイック ソート、シェルソート、ツリー ソートなどの通常はより高速なソート アルゴリズムの (最悪の場合) 境界。${\displaystyle n}$
${\displaystyle O(n^{c})}$	多項式または代数式	木結合文法解析、二部グラフの最大マッチング、 LU分解による行列式の発見
${\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$ ${\textstyle 0<\alpha <1}$	L表記または指数表記	二次ふるいまたは数体ふるいを用いた数の因数分解
${\displaystyle O(c^{n})}$ ${\textstyle c>1}$	指数関数	動的計画法を用いて巡回セールスマン問題の（正確な）解を求める；総当たり探索を用いて2つの論理文が同等かどうかを判定する
${\displaystyle O(n!)}$	階乗	巡回セールスマン問題を総当たり探索で解く；順序集合のすべての無制限順列を生成する；ラプラス展開で行列式を求める；集合のすべての分割を列挙する

この記述は、漸近的複雑性に関するより単純な式を導くために、 に弱められることがあります。これらの例の多くでは、実行時間は実際には であり、より正確な表現となっています。 ${\displaystyle f(n)=O(n!)}$ ${\displaystyle f(n)=O\left(n^{n}\right)}$ ${\displaystyle \Theta (g(n))}$

Little-o 記法

十分に大きいに対して、実変数の実数値関数または複素数値関数については 、[ 2 ] と書くこと ^{ができる。}${\displaystyle x}$ ${\displaystyle g(x)>0}$ ${\displaystyle x}$

${\displaystyle f(x)=o(g(x))\quad {\text{ as }}x\to \infty }$

つまり 、すべての正の定数εに対して、 $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0.}$$ ${\displaystyle x_{0}}$

${\displaystyle |f(x)|\leq \varepsilon g(x)\quad {\text{ for all }}x\geq x_{0}.}$

直感的に言えば、これはが よりもはるかに速く増加する、あるいはが よりもはるかに遅く増加する ことを意味します。例えば、 ${\displaystyle g(x)}$ ${\displaystyle f(x)}$ ${\displaystyle f(x)}$ ${\displaystyle g(x)}$

${\displaystyle 200x=o(x^{2})}$ そして     両方とも${\displaystyle 1/x=o(1),}$ ${\displaystyle x\to \infty .}$

の大きな値に対する関数の挙動に興味がある場合、対応する大 O 表記よりも、小 O 表記の方が強い表現になります。つまり、 の小 O である関数はすべて、ある区間 では の大 O でもありますが、 の大 O である関数すべてが の小 O であるとは限りません。たとえば、 の場合と大 O の場合では、どちらも同じです。${\displaystyle x}$ ${\displaystyle g}$ ${\displaystyle g}$ ${\displaystyle [a,\infty )}$ ${\displaystyle g}$ ${\displaystyle g}$ ${\displaystyle 2x^{2}=O(x^{2})}$ ${\displaystyle 2x^{2}\neq o(x^{2})}$ ${\displaystyle x\geq 1}$

Little-oはいくつかの算術演算を尊重します。例えば、

が非ゼロの定数である場合、そして${\displaystyle c}$ ${\displaystyle f=o(g)}$ ${\displaystyle c\cdot f=o(g)}$

もし、そして${\displaystyle f=o(F)}$ ${\displaystyle g=o(G)}$ ${\displaystyle f\cdot g=o(F\cdot G).}$

もし、そして${\displaystyle f=o(F)}$ ${\displaystyle g=o(G)}$ ${\displaystyle f+g=o(F+G)}$

これは推移関係も満たします:

もし、そして${\displaystyle f=o(g)}$ ${\displaystyle g=o(h)}$ ${\displaystyle f=o(h).}$

Little-o は有限の場合にも一般化できる: ^{[ 2 ]} の場合 言い換えれば、 を持つものに対してである。 ${\displaystyle f(x)=o(g(x))\quad {\text{ as }}x\to x_{0}}$ $${\displaystyle \lim _{x\to x_{0}}{\frac {f(x)}{g(x)}}=0.}$$ ${\displaystyle f(x)=\alpha (x)g(x)}$ ${\displaystyle \alpha (x)}$ ${\displaystyle \lim _{x\to x_{0}}\alpha (x)=0}$

この定義は、テイラー級数を用いた極限計算において特に有用である。例えば、

${\displaystyle \sin x=x-{\frac {x^{3}}{3!}}+\ldots =x+o(x^{2}){\text{ as }}x\to 0}$ 、 それで${\displaystyle \lim _{x\to 0}{\frac {\sin x}{x}}=\lim _{x\to 0}{\frac {x+o(x^{2})}{x}}=\lim _{x\to 0}1+o(x)=1}$

漸近記法

little-o に関連する関係として、漸近記法 があります。実数値関数 の場合、式 はを 意味します 。が とも同値である ことに注目することで、これを little-o に結び付けることができます 。ここで は、がゼロに向かう関数 を指しています。これは「は に漸近的である」と読みます。同じ（有限または無限）領域上の非ゼロ関数の場合、は同値関係を形成します 。 ${\displaystyle \sim }$ ${\displaystyle f,g}$ $${\displaystyle f(x)\sim g(x)\quad {\text{ as }}x\to \infty }$$ $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=1.}$$ ${\displaystyle f(x)\sim g(x)}$ ${\displaystyle f(x)=(1+o(1))g(x)}$ ${\displaystyle o(1)}$ ${\displaystyle x\to \infty }$ ${\displaystyle f(x)}$ ${\displaystyle g(x)}$ ${\displaystyle \sim }$

表記法を使用する最も有名な定理の 1 つは 、スターリングの公式です。 数論では、有名な素数定理は、最大で である素数の個数であり 、の自然対数である と述べています 。 ${\displaystyle \sim }$ $${\displaystyle n!\sim {\bigg (}{\frac {n}{e}}{\bigg )}^{n}{\sqrt {2\pi n}}\quad {\text{ as }}n\to \infty .}$$ $${\displaystyle \pi (x)\sim {\frac {x}{\log x}}\quad {\text{ as }}x\to \infty ,}$$ ${\displaystyle \pi (x)}$ ${\displaystyle x}$ ${\displaystyle \log }$ ${\displaystyle x}$

little-oと同様に、有限の極限（両側または片側）を持つバージョンもあります。たとえば、 $${\displaystyle \sin x\sim x\quad {\text{ as }}x\to 0.}$$

その他の例: 最後の漸近線はリーマンゼータ関数 の基本的な性質です 。 $${\displaystyle x^{a}=o_{a,b}(e^{bx})\quad {\text{ as }}x\to \infty ,{\text{ for any positive constants }}a,b,}$$ $${\displaystyle f(x)=g(x)+o(1)\quad \Longleftrightarrow \quad e^{f(x)}\sim e^{g(x)}\quad (x\to \infty ).}$$ $${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{n^{s}}}\sim {\frac {1}{s-1}}\quad (x\to \infty ).}$$

クヌースの小さな𝜔

最終的に正の実数値関数の場合、表記は を意味します 。 言い換えると、 です。大まかに言えば、 は よりもはるかに速く増大することを意味します。 ${\displaystyle f,g,}$ $${\displaystyle f(x)=\omega (g(x))\quad {\text{ as }}x\to \infty }$$ $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=\infty .}$$ ${\displaystyle g(x)=o(f(x))}$ ${\displaystyle f(x)}$ ${\displaystyle g(x)}$

ハーディ・リトルウッドΩ表記

1914年にGHハーディとJEリトルウッドは次のように定義される 新しい記号^{[ 12 ]を導入しました。}${\displaystyle \ \Omega ,}$

${\displaystyle f(x)=\Omega {\bigl (}\ g(x)\ {\bigr )}\quad }$ まるで​${\displaystyle \quad x\to \infty \quad }$ ${\displaystyle \quad \limsup _{x\to \infty }\ \left|{\frac {\ f(x)\ }{g(x)}}\right|>0~.}$

つまり、${\displaystyle ~f(x)=\Omega {\bigl (}\ g(x)\ {\bigr )}~}$ ${\displaystyle ~f(x)=o{\bigl (}\ g(x)\ {\bigr )}~.}$

1916年に同じ著者らは2つの新しい記号を導入し、次のように定義した。^{[ 13 ]}${\displaystyle \ \Omega _{R}\ }$ ${\displaystyle \ \Omega _{L}\ ,}$

${\displaystyle f(x)=\Omega _{R}{\bigl (}\ g(x)\ {\bigr )}\quad }$ まるで​${\displaystyle \quad x\to \infty \quad }$ ${\displaystyle \quad \limsup _{x\to \infty }\ {\frac {\ f(x)\ }{g(x)}}>0\ ;}$

${\displaystyle f(x)=\Omega _{L}{\bigl (}\ g(x)\ {\bigr )}\quad }$ まるで​${\displaystyle \quad x\to \infty \quad }$ ${\displaystyle \quad ~\liminf _{x\to \infty }\ {\frac {\ f(x)\ }{g(x)}}<0~.}$

これらの記号は1924年にE.ランダウによって同じ意味で使用されました。^{[ 14 ]}ランダウに続く著者は、同じ定義に対して異なる表記法を使用しています。^{[ 9 ]}この記号は、同じ定義を持つ現在の表記法に置き換えられ、${\displaystyle \ \Omega _{R}\ }$ ${\displaystyle \ \Omega _{+}\ }$ ${\displaystyle \ \Omega _{L}\ }$ ${\displaystyle \ \Omega _{-}~.}$

これら3つの記号は（とが両方とも満たされることを意味する）と共に、現在では解析的数論で使用されている。^{[ 9 ] [ 10 ]}${\displaystyle \ \Omega \ ,\Omega _{+}\ ,\Omega _{-}\ ,}$ ${\displaystyle \ f(x)=\Omega _{\pm }{\bigl (}\ g(x)\ {\bigr )}\ }$ ${\displaystyle \ f(x)=\Omega _{+}{\bigl (}\ g(x)\ {\bigr )}\ }$ ${\displaystyle \ f(x)=\Omega _{-}{\bigl (}\ g(x)\ {\bigr )}\ }$

簡単な例

我々は持っています

${\displaystyle \sin x=\Omega (1)\quad }$ として${\displaystyle \quad x\to \infty \ ,}$

そしてより正確には

${\displaystyle \sin x=\Omega _{\pm }(1)\quad }$ として${\displaystyle \quad x\to \infty ,~}$

ここで、左辺は と の両方であることを意味します。 ${\displaystyle \Omega _{\pm }}$ ${\displaystyle \Omega _{+}(1)}$ ${\displaystyle \Omega _{-}(1)}$

我々は持っています

${\displaystyle 1+\sin x=\Omega (1)\quad }$ として${\displaystyle \quad x\to \infty \ ,}$

そしてより正確には

${\displaystyle 1+\sin x=\Omega _{+}(1)\quad }$ として${\displaystyle \quad x\to \infty \ ;}$

しかし

${\displaystyle 1+\sin x\neq \Omega _{-}(1)\quad }$ として${\displaystyle \quad x\to \infty ~.}$

バッハマン・ランダウ記法の族

正式な定義を理解するには、 数学で使用される 論理記号のリストを参照してください。

表記	名前[ 7 ]	説明	正式な定義	コンパクトな定義 [ 4 ] [ 5 ] [ 7 ] [ 12 ] [ 15 ] [ 16 ]
${\displaystyle f(n)=o(g(n))}$	小文字の O; 小文字の Oh; 小文字の O; 小文字の Oh	fは漸近的にgに支配される（任意の定数因子に対して） ${\displaystyle k}$	${\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|\leq k\,g(n)}$	${\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=0}$
${\displaystyle f(n)=O(g(n))}$ または ${\displaystyle f(n)\ll g(n)}$ （ヴィノグラドフ記法）	ビッグO、ビッグオー、ビッグオミクロン	${\displaystyle |f|}$ はgによって上界となる（定数係数まで） ${\displaystyle k}$	${\displaystyle \exists k>0\,\forall n\in D\colon |f(n)|\leq k\,g(n)}$	${\displaystyle \sup _{n\in D}{\frac {\left|f(n)\right|}{g(n)}}<\infty }$
${\displaystyle f(n)\asymp g(n)}$ （ハーディ記法）または（クヌース記法） ${\displaystyle f(n)=\Theta (g(n))}$	（ハーディ）と同じ順序。ビッグシータ（クヌース）	fはgによって上（定数係数）と下（定数係数） の両方で制限されます。${\displaystyle k_{2}}$ ${\displaystyle k_{1}}$	${\displaystyle \exists k_{1}>0\,\exists k_{2}>0\,\forall n\in D\colon }$ ${\displaystyle k_{1}\,g(n)\leq f(n)\leq k_{2}\,g(n)}$	${\displaystyle f(n)=O(g(n))}$ そして${\displaystyle g(n)=O(f(n))}$
${\displaystyle f(n)\sim g(n)}$ （ただし、は有限）${\displaystyle n\to a}$ ${\displaystyle a}$ ${\displaystyle \infty }$ または${\displaystyle -\infty }$	漸近的同値性	fは漸近的にg に等しい	${\displaystyle \forall \varepsilon >0\,\exists n_{0}\,\forall n>n_{0}\colon \left|{\frac {f(n)}{g(n)}}-1\right|<\varepsilon }$ （この場合） ${\displaystyle a=\infty }$	${\displaystyle \lim _{n\to a}{\frac {f(n)}{g(n)}}=1}$
${\displaystyle f(n)=\Omega (g(n))}$ （クヌースの記法）、または ${\displaystyle f(n)\gg g(n)}$ （ヴィノグラドフ記法）	複雑性理論における大きなオメガ（クヌース）	fは定数倍まで gによって下界となる	${\displaystyle \exists k>0\,\forall n\in D\colon f(n)\geq k\,g(n)}$	${\displaystyle \inf _{n\in D}{\frac {f(n)}{g(n)}}>0}$
${\displaystyle f(n)=\omega (g(n))}$ として、 ${\displaystyle n\to a}$ は有限である可能性がある、または${\displaystyle a}$ ${\displaystyle \infty }$ ${\displaystyle -\infty }$	小さなオメガ; 小さなオメガ	fは漸近的に gを支配する	${\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon f(n)>k\,g(n)}$ （のために） ${\displaystyle a=\infty }$	${\displaystyle \lim _{n\to a}{\frac {f(n)}{g(n)}}=\infty }$
${\displaystyle f(n)=\Omega (g(n))}$	数論におけるビッグオメガ（ハーディ・リトルウッド）	${\displaystyle |f|}$ gは漸近的 に支配されない	${\displaystyle \exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon |f(n)|\geq k\,g(n)}$	${\displaystyle \limsup _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}>0}$

極限定義では、極限の近傍でが であると 仮定します。極限が のとき、これは十分に大きい に対して が であることを意味します。 ${\displaystyle g(n)>0}$ ${\displaystyle n}$ ${\displaystyle \infty }$ ${\displaystyle g(n)>0}$ ${\displaystyle n}$

コンピュータサイエンスと組合せ論では、大、大シータ、小、小オメガ、クヌースの大オメガ表記法が使用される。 ^{[ 3 ]} 解析的数論では、大、小、ハーディの、ハーディ–リトルウッドの大オメガ（下付き文字+、-、±の有無にかかわらず）、ヴィノグラドフの、表記法がよく使用される。 ^{[ 9 ] [ 4 ] [ 10 ]} 小オメガ表記法は解析学や数論ではあまり使用されない。 ^{[ 17 ]}${\displaystyle O}$ ${\displaystyle \Theta }$ ${\displaystyle o}$ ${\displaystyle \omega }$ ${\displaystyle \Omega }$ ${\displaystyle O}$ ${\displaystyle o}$ ${\displaystyle \asymp }$ ${\displaystyle \Omega }$ ${\displaystyle \ll }$ ${\displaystyle \gg }$ ${\displaystyle \sim }$ ${\displaystyle \omega }$

異なる表記法を用いた近似値の品質

特にコンピュータサイエンスの分野では、大表記法は漸近的な厳密な境界を記述するために多少異なる意味で使用されることが多く、特定の状況では大シータ表記法を使用する方が事実上適切である可能性があります。^{[ 18 ]} たとえば、関数 を考えるとき、以下のすべては一般に受け入れられますが、より厳しい境界（以下の番号 2、3、4 など）は通常、より緩い境界（以下の番号 1 など）よりも強く好まれます。 ${\displaystyle O}$ ${\displaystyle \Theta }$ ${\displaystyle T(n)=73n^{3}+22n^{2}+58}$

1. ${\displaystyle T(n)=O(n^{100})}$
2. ${\displaystyle T(n)=O(n^{3})}$
3. ${\displaystyle T(n)=\Theta (n^{3})}$
4. ${\displaystyle T(n)\sim 73n^{3}}$ として。${\displaystyle n\to \infty }$

これら3つの記述はすべて正しいですが、それぞれに含まれる情報は徐々に増えていきます。しかし、分野によっては、大きなO表記（上記のリストの2番目）の方が大きなTheta表記（上記のリストの3番目）よりも一般的に使用されることがあります。例えば、入力サイズ に対する新しく開発されたアルゴリズムの実行時間を とすると、アルゴリズムの発明者や利用者は、下限値や漸近的な挙動について明示的に述べずに、実行時間の上限値を設定する傾向があるかもしれません。 ${\displaystyle T(n)}$ ${\displaystyle n}$

バッハマン・ランダウ記法の拡張

コンピュータサイエンスで時々使用される別の表記法は（ソフト Oと読みます）であり、これは多対数因子を隠します。使用されている定義は 2 つあります。を の省略形として で使用する著者もいれば、 の省略形として使用する著者もいます 。^{[ 19 ]}が の多項式である 場合、違いはありません。ただし、後者の定義では、例えば と言うことができますが、前者の定義では任意の定数 に対してが可能です。後者の定義と同じ目的でO ^*と書く著者もいます。 ^{[ 20 ]}本質的には、これは大きなO表記法であり、対数因子を無視します。これは、他の超対数関数の増加率効果が、悪い実行時パフォーマンスを予測する上で、対数増加因子によってもたらされる細かい点の影響よりも重要である大きな入力パラメータの増加率爆発を示しているためです。この表記法は、手元の問題に対してあまりに厳しい制限が課されていると述べられている成長率内での「細かい点を気にする」ことを避けるためによく使われます（ 任意の定数と 任意の${\displaystyle {\tilde {O}}}$ ${\displaystyle f(n)={\tilde {O}}(g(n))}$ ${\displaystyle f(n)=O(g(n)\log ^{k}n)}$ ${\displaystyle k}$ ${\displaystyle f(n)=O(g(n)\log ^{k}g(n))}$ ${\displaystyle g(n)}$ ${\displaystyle n}$ ${\displaystyle n2^{n}={\tilde {O}}(2^{n})}$ ${\displaystyle \log ^{k}n={\tilde {O}}(1)}$ ${\displaystyle k}$ ${\displaystyle \log ^{k}n=o(n^{\varepsilon })}$ ${\displaystyle k}$ ${\displaystyle \varepsilon >0.}$

また、L表記は次のように定義される。

${\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }},}$

は、 に関して多項式と指数関数の間に位置する関数に便利です。 ${\displaystyle \log n}$

一般化と関連する用法

任意のノルムベクトル空間に値を取る関数への一般化は（絶対値をノルムに置き換えるだけで）単純である。ここで、 と は同じ空間に値を取る必要はない。任意の位相群に値を取る関数への一般化も可能である。「極限過程」は、任意のフィルタ基数を導入することで、すなわち有向ネットと に一般化することもできる。この表記法は、極めて一般的な空間における導関数と微分可能性、そして関数の（漸近的）同値性 を定義するために使用できる。${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle g}$ ${\displaystyle x\to x_{0}}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle o}$

${\displaystyle f\sim g\iff (f-g)\in o(g)}$

これは同値関係であり、上記の関係「は」よりも制限的な概念です。 （ とが正の実数値関数である場合、 に簡約されます。）たとえば、は ですが、 です 。 ${\displaystyle f}$ ${\displaystyle \Theta (g)}$ ${\displaystyle \lim f/g=1}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle 2x=\Theta (x)}$ ${\displaystyle 2x-x\neq o(x)}$

歴史

ボア・レイモンド、バッハマン・ランダウ、ハーディ、ヴィノグラドフ、クヌースの表記法の歴史を概説します。

1870年、ポール・デュ・ボワ＝レーモン^{[ 21 ]}は、、、を それぞれ と 定義 した 。これらは広く採用されず、今日では使われていない。最初の と 3 番目の は対称性があり、は と同じ意味である。後に、ランダウはより狭義の の極限が 1 に等しいという考え方を採用した。これらの表記法はいずれも今日では使われていない。 ${\displaystyle f(x)\succ \phi (x)}$ ${\displaystyle f(x)\sim \phi (x)}$ ${\displaystyle f(x)\prec \phi (x)}$ $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{\phi (x)}}=\infty ,\quad \lim _{x\to \infty }{\frac {f(x)}{\phi (x)}}>0,\quad \lim _{x\to \infty }{\frac {f(x)}{\phi (x)}}=0.}$$ ${\displaystyle f(x)\prec \phi (x)}$ ${\displaystyle \phi (x)\succ f(x)}$ ${\displaystyle \sim }$ ${\displaystyle f(x)/\phi (x)}$

記号Oは、数論者ポール・バッハマンが1894年に著書『解析数論』第2巻で初めて導入しました。^{[ 1 ]}数論者エドムンド・ランダウがこれを採用し、1909年にoという表記法を導入しました。^{[ 2 ]}そのため、現在では両方ともランダウ記号と呼ばれています。これらの表記法は、1950年代の応用数学において漸近解析に使用されました。^{[ 22 ]} 記号（「 oではない」という意味で）は、1914年にハーディとリトルウッドによって導入されました。^{[ 12 ]}ハーディとリトルウッドは1916年に（「右」）と（「左」）という記号も導入しました。 ^{[ 13 ]}この表記法は、少なくとも1950年代以降、数論においてある程度一般的に使用されるようになりました。^{[ 23 ]}${\displaystyle \Omega }$ ${\displaystyle \Omega _{R}}$ ${\displaystyle \Omega _{L}}$ ${\displaystyle \Omega }$

記号 は、以前にも異なる意味で使用されていましたが^{[ 21 ]} 、 1909年にランダウによって^{[ 2 ]}、1910年にハーディによって現代的な定義が与えられました^{[ 5 ]。}ハーディは、論文の同じページで、記号 を定義しました。ここで、 は、 と の両方が満たされることを意味します。この表記法は現在でも解析的整数論で使用されています^{[ 24 ] [ 10 ]} ハーディは、論文の中で、記号 も提案しました。ここで、 は、ある定数に対してとなることを意味します（これはボア・レーモンの表記 に対応します）。 ${\displaystyle \sim }$ ${\displaystyle \asymp }$ ${\displaystyle f(x)\asymp g(x)}$ ${\displaystyle f(x)=O(g(x))}$ ${\displaystyle g(x)=O(f(x))}$ ${\displaystyle \mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} }$ ${\displaystyle f\mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} g}$ ${\displaystyle f\sim Kg}$ ${\displaystyle K\not =0}$ ${\displaystyle f\sim g}$

1930年代にヴィノグラドフ^{[ 6 ]}は、 とという表記法を普及させました。これらはどちらも を意味します 。この表記法は解析的数論における標準となりました。^{[ 4 ]}${\displaystyle f(x)\ll g(x)}$ ${\displaystyle g(x)\gg f(x)}$ ${\displaystyle f(x)=O(g(x))}$

1970年代にビッグOはドナルド・クヌースによってコンピュータサイエンスの分野で普及した。クヌースはハーディのオメガ表記法に別の表記法を提案し、ハーディとリトルウッドのオメガ表記法に別の定義を提案した。^{[ 7 ]}${\displaystyle f(x)=\Theta (g(x))}$ ${\displaystyle f(x)\asymp g(x)}$

^{ハーディは1910年の小冊子『無限大の秩序』 [ 5 ]}でこれらの記号を導入し、ボイド＝レーモンドの記号（および既に述べた他の記号）を提唱したが、実際に使用したのは3本の論文（1910年から1913年）のみであった。残りの約400本の論文と著書では、一貫してランダウ記号Oとoを用いていた。^{[ 25 ]} ハーディの記号とは 現在では使用されていない。 ${\displaystyle \preccurlyeq }$ ${\displaystyle \prec }$ ${\displaystyle \preccurlyeq }$ ${\displaystyle \mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} }$

表記に関する事項

矢印

数学において、 のような表現は極限の存在を示します。大文字のO表記法や関連表記法では 、小文字のO表記法や、 その他の表記法とは異なり、暗黙の極限は存在しません。 のような表記法は、表記法の乱用とみなされる可能性があります。 ${\displaystyle x\to \infty }$ ${\displaystyle \Omega ,\Theta ,\gg ,\ll ,\asymp }$ ${\displaystyle \sim }$ ${\displaystyle \omega }$ ${\displaystyle f(x)=O(g(x))\;\;(x\to \infty )}$

等号

は、記法の乱用であると考える者もいる。なぜなら、等号の使用は、この文が持たない対称性を示唆し、誤解を招く可能性があるからだ。de Bruijnが言うように、 は真だが、はそうではない。^{[ 26 ]} Knuthは、このような文を「一方向性等式」と表現している。なぜなら、もし左右を逆にできると、「 恒等式とから、のようなばかげたことを推論できるからだ。 」 ^{[ 27 ]} Knuthは別の手紙でも、次のことを指摘している。 ^{[ 28 ]}${\displaystyle f(x)=O(g(x))}$ ${\displaystyle O(x)=O(x^{2})}$ ${\displaystyle O(x^{2})=O(x)}$ ${\displaystyle n=n^{2}}$ ${\displaystyle n=O(n^{2})}$ ${\displaystyle n^{2}=O(n^{2})}$

等号はこのような表記法に対して対称ではありません [この表記法では、] 数学者は英語の単語「is」と同じように「=」記号を慣習的に使用します。アリストテレスは人間ですが、人間は必ずしもアリストテレスであるとは限りません。

これらの理由から、集合記法を用いて と書き、「は の要素である」または「は集合に含まれる 」と読み、を となるすべての関数のクラスと 考えることを 提唱する人もいます。^{[ 27 ]}しかし、等号の使用は慣例です。^{[ 26 ] [ 27 ]} そして、より複雑な形式の式ではより便利です。 ${\displaystyle f(x)\in O(g(x))}$ ${\displaystyle f(x)}$ ${\displaystyle O(g(x))}$ ${\displaystyle f(x)}$ ${\displaystyle O(g(x))}$ ${\displaystyle O(g(x))}$ ${\displaystyle h(x)}$ ${\displaystyle h(x)=O(g(x))}$ $${\displaystyle f(x)=g(x)+O(h(x))=O(k(x)).}$$

^数論で広く用いられている ヴィノグラドフ記法のと は、 この欠陥を抱えていない。なぜなら、これらの記法は、big-O が等式 ではなく不等式 を表すことをより明確に示しているからである^{。また、これらの記法は}、 big - ^O記法にはない対称性も備えている。 つまり、 は と同じ意味である。組合せ論やコンピュータサイエンスでは、これらの記法はほとんど見られない。^{[ 3 ]}${\displaystyle \ll }$ ${\displaystyle \gg }$ ${\displaystyle f(x)\ll g(x)}$ ${\displaystyle g(x)\gg f(x)}$

組版

ビッグオーは、以下の例のように、イタリック体の大文字「O 」として表記されます。^{[ 29 ] [ 30 ]} TeX では、数式モードで「O」と入力するだけで表示されます。ギリシャ語で「バッハマン・ランダウ」と呼ばれる表記法とは異なり、特別な記号は必要ありません。しかし、一部の著者はカリグラフィ的な表記法を使用しています。^{[ 31 ] [ 32 ]}${\displaystyle O(n^{2})}$ ${\displaystyle {\mathcal {O}}}$

大文字の「O」は元々「o​​rder of」（"Ordnung"、Bachmann 1894）を表し、ラテン文字です。BachmannもLandauもこれを「Omicron」と呼ぶことはありません。この記号はずっと後（1976年）、Knuthによって大文字の「omicron」とみなされました[7]。これはおそらく、記号Ωの定義に由来すると思われます。数字^のゼロは使用すべきではありません。

参照

• 漸近的計算複雑性
• 漸近展開：テイラーの公式を一般化した級数による関数の近似
• 漸近的最適アルゴリズム：問題の下限値の定数内に漸近的に上限値を持つアルゴリズムを説明するためによく使われるフレーズ
• 確率表記におけるビッグO：O _p、o _p
• 下限と上限：この記事で使用されているいくつかの限界表記法の説明
• マスター定理（アルゴリズムの解析） : ビッグO記法を用いた分割統治再帰アルゴリズムの解析
• ナハビンの定理：積分変換の収束領域を明示できるように、複素解析関数を限定する正確な方法
• 近似の順序
• 精度の順序
• 数学演算の計算複雑さ

参考文献と注釈

1. バックマン、ポール(1894)。Analytische Zahlentheorie [解析的整数論] (ドイツ語)。 Vol. 2. ライプツィヒ：トイブナー。
2. ランドー、エドマンド(1909)。Handbuch der Lehre von der Verreilung der Primzahlen [素数の分布理論に関するハンドブック] (ドイツ語)。ライプツィヒ: BG トイブナー; 1974 年にチェルシー社から 2 冊一体として再版され、ポール T. ベイトマン博士による付録が付けられました。59～ 63ページ 。
3. コーメン, トーマス・H. ;レイソン, チャールズ・E. ;リベスト, ロナルド・L. ;スタイン, クリフォード(2022). 「実行時間の特徴づけ」.アルゴリズム入門（第4版）. MIT Press and McGraw-Hill. ISBN 978-0-262-53091-0。
4. イワニエツ, ヘンリク; コワルスキー, エマニュエル (2004).解析的数論. アメリカ数学会.
5. ハーディ、GH（1910年） 『無限の秩序：ポール・デュ・ボワ＝レーモンの「無限計算」』ケンブリッジ大学出版局、2頁。
6. ヴィノグラドフ、マトヴェーヴィチ(1934)。 「ワーリングの問題におけるG ( n )の新しい推定」。 Doklady Akademii Nauk SSSR (ロシア語)。5（5～ 6）：249～ 253。

   英語に翻訳されています：

   ヴィノグラドフ、マトヴェエヴィッチ（1985年）。選集／イヴァン・マトヴェエヴィッチ・ヴィノグラドフ。ソ連科学アカデミー・ステクロフ数学研究所がヴィノグラドフの90歳の誕生日を記念して編纂。シュプリンガー・フェアラーク。
7. ドナルド・クヌース（1976年4月～6月）「ビッグ・オミクロン、ビッグ・オメガ、ビッグ・シータ」 SIGACTニュース8 ( 2): 18～ 24. doi : 10.1145/1008328.1008329 . S2CID 5230246 . 
8. Sipser, Michael (2012).計算理論入門（第3版）. ボストン, MA: PWS Publishin.
9. Ivić, A. (1985).リーマンゼータ関数. John Wiley & Sons. 第9章.
10. ジェラルド・テネンバウム「解​​析的および確率的数論入門」『表記法』、xxiiiページ。アメリカ数学会、プロビデンス、ロードアイランド州、2015年。
11. ザイデル、ライムンド（1991）、「台形分解の計算と多角形の三角形化のための単純かつ高速な増分ランダム化アルゴリズム」、計算幾何学、1：51-64、Ci​​teSeerX 10.1.1.55.5877、doi：10.1016/0925-7721(91)90012-4 
12. Hardy, GH ; Littlewood, JE (1914). 「ディオファントス近似に関するいくつかの問題：第2部楕円θ 関数に関連する三角級数」 Acta Mathematica 37 : 225. doi : 10.1007/BF02401834 . 2018年12月12日時点のオリジナルよりアーカイブ。 2017年3月14日閲覧。
13. Hardy, GH ; Littlewood, JE (1916). 「リーマンゼータ関数の理論と素数分布の理論への貢献」. Acta Mathematica . 41 : 119–196 . doi : 10.1007/BF02422942 .
14. E. ランダウ(1924)。 「Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV」[既知の領域の格子点の数について]。ナクル。ゲゼル。ウィス。ゴット。数学物理学。 (ドイツ語): 137–150。
15. バルカサル、ホセ L.ガバロ、ホアキン。「下限と上限によって指定される不均一な複雑さのクラス」(PDF)。RAIRO – 理論情報学とアプリケーション – Informatique Théorique et Applications。23 (2): 180. ISSN 0988-3754。2017 年 3 月 14 日のオリジナルからアーカイブ(PDF) 。2017 年3 月 14 日に取得– Numdam 経由。 
16. Cucker, Felipe; Bürgisser, Peter (2013). 「A.1 Big Oh, Little Oh, and Other Comparisons」 . Condition: The Geometry of Numerical Algorithms . Berlin, Heidelberg: Springer. pp.  467– 468. doi : 10.1007/978-3-642-38896-5 . ISBN 978-3-642-38896-5。
17. 例えば、 Hildebrand, AJ 「漸近的記法」（PDF）では省略されています。数学部。漸近的解析法。Math 595、2009年秋。イリノイ州アーバナ：イリノイ大学。2017年3月14日時点のオリジナルからアーカイブ（PDF） 。 2017年3月14日閲覧。
18. Cormen et al. 2022、57頁。
19. コーメンら。 2022、p. 74〜75。
20. Andreas Björklund、Thore Husfeldt、Mikko Koivisto (2009). 「包含-除外によるセット分割」(PDF) . SIAM Journal on Computing . 39 (2): 546– 563. doi : 10.1137/070683933 . 2022年2月3日時点のオリジナルよりアーカイブ(PDF) . 2022年2月3日閲覧.セクション2.3、p.551を参照してください。
21. ボワ＝レイモンド、ポール・デュ (1870)。「機能の無限の偉大なる相対性」。アンナリ ディ マテマティカ、セリエ 2。4 : 338–353。土井: 10.1007/BF02420041。
22. エルデイ, A. (1956).漸近展開. クーリエ社. ISBN 978-0-486-60318-6。。
23. ECティッチマーシュ『リーマンゼータ関数の理論』（オックスフォード、クラレンドン出版社、1951年）
24. ハーディ, GH;ライト, EM (2008) [第1版 1938年]. 「1.6. いくつかの表記法」. 『数論入門』 . D.R. ヒース＝ブラウンとJ.H. シルバーマンによる改訂版、アンドリュー・ワイルズによる序文（第6版）. オックスフォード: オックスフォード大学出版局. ISBN 978-0-19-921985-8。
25. ハーディ, GH (1966–1979). GHハーディ論文集（JEリトルウッドらとの共著を含む）全7巻. クラレンドン・プレス, オックスフォード.
26. de Bruijn、NG (1958)。分析における漸近的手法。アムステルダム: 北オランダ。5 ～ 7ページ 。ISBN 978-0-486-64221-5. 2023年1月17日時点のオリジナルよりアーカイブ。2021年9月15日閲覧。
27. グラハム、ロナルド、クヌース、ドナルド、パタシュニック、オーレン(1994).コンクリート数学(第2版). マサチューセッツ州レディング: アディソン・ウェスレー. p. 446. ISBN 978-0-201-55802-9. 2023年1月17日時点のオリジナルよりアーカイブ。2016年9月23日閲覧。
28. Donald Knuth (1998年6～7月). "Teach Calculus with Big O" (PDF) . Notices of the American Mathematical Society . 45 (6): 687. 2021年10月14日時点のオリジナルよりアーカイブ(PDF) . 2021年9月5日閲覧。（完全版は2008年5月13日にWayback Machineにアーカイブされています）
29. Donald E. Knuth, The art of computer programming. 第1巻. 基本アルゴリズム, 第3版, Addison Wesley Longman, 1997年. セクション1.2.11.1.
30. Ronald L. Graham、Donald E. Knuth、Oren Patashnik、「Concrete Mathematics: A Foundation for Computer Science（第2版）」、Addison-Wesley、1994年。セクション9.2、p.443。
31. Sivaram Ambikasaran と Eric Darve、「部分階層的半分離可能行列の高速直接ソルバー」、 J. Scientific Computing 57 (2013)、第3号、477–501ページ。${\displaystyle {\mathcal {O}}(N\log N)}$
32. Saket SaurabhとMeirav Zehavi、「-Max-Cut:時間アルゴリズムと多項式カーネル」、 Algorithmica 80 (2018)、第12号、3844–3860。${\displaystyle (k,n-k)}$ ${\displaystyle {\mathcal {O}}^{*}(2^{p})}$

注記

1. 入力の「サイズ」は通常、解くべき問題の難易度を示す指標として用いられます。答えを計算する（つまり問題を「解く」）ために必要な[実行]時間と[メモリ]容量は、問題のそのインスタンスの難易度を示すものと考えられています。計算複雑性理論においては、ビッグ記法は、入力[データストリーム]のサイズ、必要な[実行]時間、必要な[メモリ]容量の3つすべてに対する[「桁数」の上限]として用いられます。${\displaystyle O}$

さらに読む

• ドナルド・クヌース(1997). 「1.2.11: 漸近的表現」.基礎アルゴリズム. コンピュータプログラミングの技法. 第1巻 (第3版). Addison-Wesley. ISBN 978-0-201-89683-1。
• シプサー、マイケル(1997).計算理論入門. PWS Publishing. pp.  226–228 . ISBN 978-0-534-94728-6。
• Avigad, Jeremy; Donnelly, Kevin (2004). Isabelle/HOLにおけるO記法の形式化(PDF) . 国際自動推論合同会議. doi : 10.1007/978-3-540-25984-8_27 .
• Black, Paul E. (2005年3月11日). Black, Paul E. (編). 「big-O記法」 .アルゴリズムとデータ構造の辞書. 米国国立標準技術研究所. 2006年12月16日閲覧.
• ブラック、ポール・E. (2004年12月17日). ブラック、ポール・E. (編). 「little-o記法」 .アルゴリズムとデータ構造の辞書. 米国国立標準技術研究所. 2006年12月16日閲覧.
• Black, Paul E. (2004年12月17日). Black, Paul E. (編). 「Ω」 .アルゴリズムとデータ構造の辞書. 米国国立標準技術研究所. 2006年12月16日閲覧.
• Black, Paul E. (2004年12月17日). Black, Paul E. (編). 「ω」 .アルゴリズムとデータ構造の辞書. 米国国立標準技術研究所. 2006年12月16日閲覧.
• Black, Paul E. (2004年12月17日). Black, Paul E. (編). 「Θ」 .アルゴリズムとデータ構造の辞書. 米国国立標準技術研究所. 2006年12月16日閲覧.

外部リンク

• 数列の成長 — OEIS（整数数列オンライン百科事典）Wiki
• 漸近記法入門
• Big-O記法 – 何に役立つのか
• 一次導関数の中心差分法の精度におけるBig Oの例
• アルゴリズムの複雑性分析へのやさしい入門