ビッグオー表記

ビッグオー表記法は、引数が特定の値または無限大に向かう関数の極限動作を記述する数学表記法である。ビッグオーは、ドイツの数学者ポール・バッハマン^[1]、エドモンド・ランダウ^[2]らによって発明された表記法ファミリーの一員であり、総称してバッハマン・ランダウ表記法または漸近表記法と呼ばれる。文字Oは、近似の順序を意味するOrdnungを表すためにバッハマンによって選ばれた。

コンピュータサイエンスでは、ビッグオー表記法は、入力サイズの増加に応じて実行時間やメモリ要件がどのように増加するかに基づいてアルゴリズムを分類するために使用されます。 ^[3]解析的整数論 では、ビッグオー表記法は算術関数とよりよく理解されている近似値との差の境界を表現するためによく使用されます。そのような差の有名な例としては、素数定理の剰余項があります。ビッグオー表記法は、他の多くの分野でも同様の推定値を提供するために使用されています。

ビッグ O 表記法は、関数をその成長率に応じて特徴付けます。つまり、同じ漸近的成長率を持つ異なる関数は、同じ O 表記法を使用して表すことができます。文字 O が使用されるのは、関数の成長率が関数の次数とも呼ばれるためです。ビッグ O 表記法による関数の記述は、通常、関数の成長率の 上限のみを提供します。

ビッグO表記法に関連して、 o、Ω、ω、Θなどの記号を使用して漸近的成長率の他の種類の境界を記述するいくつかの関連表記法があります。^[3]

推定する関数を実数値または複素数値関数とし、比較関数を実数値関数とします。両方の関数が、正の実数の無制限なサブセット上で定義され、の十分に大きいすべての値に対して非ゼロ（多くの場合、厳密に正であるが、必ずしもそうではない）であるとします。 ^[4]と書き 、これは「は の大 O である」、またはより一般的には「は のオーダーである」 と読み、の絶対値が、 の十分に大きいすべての値に対しての絶対値の正の定数倍以下である場合に、つまり 、 となる正の実数および実数が存在する場合です。 多くの文脈では、変数が無限大またはゼロになるときの成長率に関心があるという仮定は明言されず、より単純に と書きます 。 表記法は、ある実数（多くの場合） の付近での の挙動を記述するためにも使用できます。で定義されるすべての に対して となる正の数およびが存在する場合、 と言い、 が 十分に大きい （または小さい） の値に対して が非ゼロである 場合に、 これら の定義は両方とも、の優れた極限を使用して統一できます。 つまり、 のあらゆる近傍には、無限に多くの共通点が存在することになります。さらに、 の下限と上限に関する記事で指摘したように、 は(少なくとも拡張された実数直線上では) 常に存在します。 ${\displaystyle f,}$${\displaystyle \ g\,}$ ${\displaystyle g(x)}$${\displaystyle x.}$$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to \infty }$$${\displaystyle \ f(x)\ }$${\displaystyle g(x)}$${\displaystyle f(x)}$${\displaystyle g(x)}$${\displaystyle f(x)}$${\displaystyle g(x)}$${\displaystyle x.}$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}}$${\displaystyle M}$${\displaystyle x_{0}}$$${\displaystyle |f(x)|\leq M\ |g(x)|\quad {\text{ for all }}x\geq x_{0}~.}$$${\displaystyle \ x\ }$$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}.}$$${\displaystyle f}$${\displaystyle a}$${\displaystyle a=0}$$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}\ x\to a}$$${\displaystyle \delta }$${\displaystyle M}$${\displaystyle x}$${\displaystyle 0<|x-a|<\delta ,}$ $${\displaystyle |f(x)|\leq M|g(x)|.}$$${\displaystyle g(x)}$${\displaystyle x,}$$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}\ x\to a}$$$${\displaystyle \limsup _{x\to a}{\frac {\left|f(x)\right|}{\left|g(x)\right|}}<\infty .}$$ ${\displaystyle a}$${\displaystyle \infty }$${\displaystyle f}$${\displaystyle g,}$${\displaystyle a}$${\displaystyle \textstyle \limsup _{x\to a}}$

コンピュータサイエンスでは、もう少し制限された定義が一般的です。との両方が、正の整数の無限集合から非負の実数への関数であることが要求されます。そして、すべての^[5]に対して${\displaystyle f}$${\displaystyle g}$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}}$${\displaystyle M}$${\displaystyle n_{0}}$${\displaystyle |f(n)|\leq M|g(n)|}$${\displaystyle n\geq n_{0}.}$

通常の使用法では、O表記は漸近的であり、つまり非常に大きなxを指します。この設定では、「最も急速に」増加する項の寄与により、最終的には他の項が無関係になります。結果として、次の簡略化ルールを適用できます。

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

たとえば、f ( x ) = 6 x ⁴ − 2 x ³ + 5とし、 x が無限大に近づくにつれて増加率を表すために、 O表記法を使用してこの関数を簡略化するとします。 この関数は、 6 x ⁴、−2 x ³、および5の 3 つの項の合計です。 これら 3 つの項のうち、増加率が最も高いのは、 xの関数として最大の指数を持つ項、つまり6 x ⁴です。 ここで、2 番目の規則を適用できます。6 x ^{4 は、最初の因数が}xに依存しない6とx ⁴の積です。 この因数を省略すると、簡略化された形式x ^{4になります。 したがって、} f ( x ) はx ⁴の「大きな O」であると言えます。 数学的には、 f ( x ) = O ( x ⁴ )と書くことができます。この計算は、正式な定義を使って確認することができます。f ( x ) = 6 x ⁴ − 2 x ³ + 5、g ( x ) = x ^{4とします。上記の正式な定義を適用すると、} f ( x ) = O ( x ⁴ )というステートメントは、 実数x ₀と正の実数Mの適切な選択とすべてのx > x ₀に対して、その展開と同等です 。これを証明するには、x ₀ = 1、M = 13とします。すると、すべてのx > x ₀に対して、 次のように なります。$${\displaystyle |f(x)|\leq Mx^{4}}$$$${\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}.}$$

Big O 表記法には、主に 2 つの適用領域があります。

• 数学では、特に切断されたテイラー級数や漸近展開の場合に、有限級数が与えられた関数にどれだけ近似するかを説明するためによく使用されます。
• コンピュータサイエンスでは、アルゴリズムの分析に役立ちます。^[3]

どちらのアプリケーションでも、 O (·)内に現れる関数g ( x )は、通常、定数因子と低次の項を省略して、可能な限り単純になるように選択されます。

この表記法には、形式的には近いが、著しく異なる 2 つの用法がある: ^{[引用が必要]}

• 無限漸近
• 無限小漸近。

ただし、この区別は適用上のものであり、原則上のものではありません。「big O」の正式な定義はどちらの場合も同じで、関数の引数の制限が異なるだけです。^{[独自の研究? ]}

Big O 表記法は、アルゴリズムの効率性を分析するときに便利です。たとえば、サイズnの問題を完了するのにかかる時間 (またはステップ数) は、 T ( n ) = 4 n ² − 2 n + 2であることがわかります。nが大きくなるにつれて、n ² 項が支配的になり、他のすべての項を無視できるようになります。たとえば、 n = 500の場合、項4 n ²は項2 nの 1000 倍の大きさになります。後者を無視しても、ほとんどの目的では式の値にほとんど影響はありません。さらに、項n ³またはn ⁴を含む式など、他の順序の式と比較する場合、係数は無関係になります。 T ( n ) = 1,000,000 n ²であっても、U ( n ) = n ³であれば、 n が1,000,000よりも大きくなると、後者は常に前者を超えます。T (1,000,000) = 1,000,000 ³ = U (1,000,000)。さらに、ステップ数はアルゴリズムが実行されるマシンモデルの詳細に依存しますが、異なるタイプのマシンでは、通常、アルゴリズムを実行するために必要なステップ数は一定の係数だけ異なります。したがって、ビッグO表記法は残りの部分を表現します。

${\displaystyle T(n)=O(n^{2})}$

または

${\displaystyle T(n)\in O(n^{2})}$

そして、アルゴリズムの時間計算量はn ²のオーダーであると言う。記号「=」は、通常の数学的な意味で「等しい」を表すのではなく、より口語的な「である」を表すため、2番目の表現の方が正確であると考えられることがある（以下の「等号」の説明を参照）。一方、1番目は表記法の乱用であると考える人もいる。^[6]

Big O は、数学関数の近似値における誤差項を記述するためにも使用できます。最も重要な項は明示的に記述され、最も重要でない項は 1 つの Big O 項にまとめられます。たとえば、 xが小さい 場合に有効な指数級数とその 2 つの式を考えてみましょう。

${\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{as }}x\to 0\\[4pt]&=1+x+O(x^{2})&{\text{as }}x\to 0\end{aligned}}}$

真ん中の式（ O ( x ³ )のもの）は、 xが 0 に十分近い場合、誤差e ^x − (1 + x + x ² /2) の絶対値が最大で定数倍 | x ³ |になることを意味します。

関数f が他の関数の有限和として表せる場合、最も速く増加する関数がf ( n )の次数を決定します。たとえば、

${\displaystyle f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .}$

特に、関数がnの多項式で制限される場合、n が無限大に近づくにつれて、多項式の低次の項を無視することができます。集合O ( n ^c )とO ( c ⁿ )は非常に異なります。c が 1 より大きい場合、後者は非常に速く増加します。任意のcに対してn ^cよりも速く増加する関数は、超多項式 と呼ばれます。形式c ⁿのどの指数関数よりも遅く増加する関数は、準指数と呼ばれます。アルゴリズムは、超多項式かつ準指数的な時間を必要とする場合があります。この例としては、整数因数分解の最も高速な既知のアルゴリズムや関数n ^{log n など}があります。

対数内のnの累乗は無視できます。集合O (log n ) はO (log( n ^c ))とまったく同じです。対数は定数係数だけ異なるため ( log( n ^c ) = c log nであるため)、大きな O 表記ではそれが無視されます。同様に、異なる定数底を持つ対数は同等です。一方、異なる底を持つ指数は同じ順序ではありません。たとえば、2 ⁿと3 ^{n は}同じ順序ではありません。

単位を変更すると、結果として得られるアルゴリズムの順序に影響する場合と、影響しない場合があります。単位を変更することは、適切な変数に、出現するすべての定数を掛けることと同じです。たとえば、アルゴリズムがn ²の順序で実行される場合、n をcnに置き換えることは、アルゴリズムがc ² n ²の順序で実行されることを意味し、大文字の O 表記では定数c ^{2 は無視されます。これは、} c ² n ² = O( n ² )と記述できます。ただし、アルゴリズムが2 ⁿの順序で実行される場合、n をcnに置き換えると、 2 ^cn = (2 ^c ) ⁿになります。これは、一般に2 ⁿと同じではありません。変数を変更すると、結果として得られるアルゴリズムの順序にも影響する場合があります。たとえば、入力数xの桁数nで測定されたアルゴリズムの実行時間がO ( n )である場合、入力数x自体の関数として測定された実行時間はO (log x )です。これは、n = O (log x )であるためです。

${\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(fg)}$

であれば、となります。したがって、であれば、 となります。言い換えると、この 2 番目のステートメントは、が凸錐であることを示しています。 ${\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}\in O(g)}$${\displaystyle O(g)}$

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

大きなO（および小さなo、Ωなど）は、複数の変数にも使用できます。複数の変数に対する大きなOを正式に定義するには、とが のサブセット上で定義された2つの関数であるとします。 ${\displaystyle f}$${\displaystyle g}$${\displaystyle \mathbb {R} ^{n}}$

${\displaystyle f(\mathbf {x} ){\text{ is }}O(g(\mathbf {x} ))\quad {\text{ as }}\mathbf {x} \to \infty }$

定数 と が存在し、すべての に対してであり、いくつかのに対してであるとき、かつその場合に限る^[7]同様に、いくつかの に対して で ある条件はと書くことができ、ここで はチェビシェフノルムを表す。例えば、 ${\displaystyle M}$${\displaystyle C>0}$${\displaystyle |f(\mathbf {x} )|\leq C|g(\mathbf {x} )|}$${\displaystyle \mathbf {x} }$${\displaystyle x_{i}\geq M}$${\displaystyle i.}$${\displaystyle x_{i}\geq M}$${\displaystyle i}$${\displaystyle \|\mathbf {x} \|_{\infty }\geq M}$${\displaystyle \|\mathbf {x} \|_{\infty }}$

${\displaystyle f(n,m)=n^{2}+m^{3}+O(n+m)\quad {\text{ as }}n,m\to \infty }$

定数CとMが存在し、

${\displaystyle |f(n,m)-(n^{2}+m^{3})|\leq C|n+m|}$

またはのいずれかが成り立つときはいつでも。この定義により、 のすべての座標が無限大まで増加することが許される。特に、次の文は ${\displaystyle m\geq M}$${\displaystyle n\geq M}$${\displaystyle \mathbf {x} }$

${\displaystyle f(n,m)=O(n^{m})\quad {\text{ as }}n,m\to \infty }$

（すなわち、）は、 ${\displaystyle \exists C\,\exists M\,\forall n\,\forall m\,\cdots }$

${\displaystyle \forall m\colon ~f(n,m)=O(n^{m})\quad {\text{ as }}n\to \infty }$

（すなわち、）。 ${\displaystyle \forall m\,\exists C\,\exists M\,\forall n\,\cdots }$

この定義では、関数が定義されているサブセットは、一変量設定から多変量設定にステートメントを一般化するときに重要です。たとえば、およびの場合、およびを に制限すると、になりますが、 上で定義されている場合はそうではありません。 ${\displaystyle f(n,m)=1}$${\displaystyle g(n,m)=n}$${\displaystyle f(n,m)=O(g(n,m))}$${\displaystyle f}$${\displaystyle g}$${\displaystyle [1,\infty )^{2}}$${\displaystyle [0,\infty )^{2}}$

これはビッグOを多変数関数に一般化した唯一の例ではなく、実際には定義の選択に矛盾がある。^[8]

上で定義した「 f ( x )  はO [ g ( x ) ]  である」という文は、通常f ( x ) = O [ g ( x ) ]  と表記されます。これは表記法の乱用であると考える人もいます。等号の使用は、この文にはない対称性を示唆するため誤解を招く可能性があるからです。de Bruijn が言うように、O [ x ] = O [ x ² ]  は真ですが、O [ x ² ] = O [ x ]  は真ではありません。^[9] Knuth は、こ​​のような文を「一方向の等式」と表現しています。なぜなら、もし両側を逆にできるなら、「n = O [ n ² ]  とn ² = O [ n ² ]  という恒等式からn = n ²のようなばかげたことを推論できる」からです。^[10] Knuth は別の手紙でも、                 

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

これらの理由から、 O [ g ( x ) ]  を、ある正の実数 C に対して| h ( x ) | ≤ C | g ( x ) | となるすべての関数 h ( x )のクラスと  考え、集合記法を使用してf ( x )   ∈ O [ g ( x ) ] （「 f ( x ) は O [ g ( x ) ] の要素である」または「f ( x )  は集合O [ g (   x ) ]に含まれる」と読む  ）と書く方が正確である。[ 10 ]ただし、等号  の^使用は慣例となっている。[ ^9] [ ^10]               

ビッグオー記法は、より複雑な方程式で他の算術演算子と組み合わせて使用​​することもできます。たとえば、h ( x ) + O ( f ( x )) は、 h ( x )の増加と、増加がf ( x )に制限される部分を持つ関数の集合を表します。したがって、

${\displaystyle g(x)=h(x)+O(f(x))}$

同じことを表す

${\displaystyle g(x)-h(x)=O(f(x)).}$

n個の要素のセットを操作するアルゴリズムが開発されているとします。開発者は、入力セットの要素数に基づいて、アルゴリズムの実行にかかる時間 (任意の時間測定単位) を表す関数T ( n ) を見つけたいと考えています。アルゴリズムは、最初にサブルーチンを呼び出してセット内の要素をソートし、次に独自の操作を実行することで機能します。ソートには既知の時間計算量O ( n ² ) があり、サブルーチンの実行後、アルゴリズムは終了するまでにさらに55 n ³ + 2 n + 10ステップを実行する必要があります。したがって、アルゴリズムの全体的な時間計算量は、 T ( n ) = 55 n ³ + O ( n ² )と表すことができます。ここで、 2 n + 10という項は、より速く増加するO ( n ² ) に含まれます。この場合も、この使用法では "=" 記号の正式な意味の一部が無視されますが、大きな O 表記を一種の便利なプレースホルダーとして使用できるようになります。

より複雑な用法では、O (·) は方程式の異なる場所に現れ、各辺に複数回現れることもあります。たとえば、次が について当てはまります。 このようなステートメントの意味は次のとおりです。左辺の各O (·)を満たす任意の関数に対して、右辺の各O (·) を満たすいくつかの関数が存在し、これらすべての関数を方程式に代入すると、両辺が等しくなります。たとえば、上記の 3 番目の方程式は、「任意の関数f ( n ) = O (1) に対して、 n ^{f ( n ) =} g ( n )となる関数g ( n ) = O ( e n ⁾が存在する」ことを意味します。上記の「集合表記法」では、左辺で表される関数のクラスが右辺で表される関数のクラスのサブセットであることを意味します。この用法では、「=」は正式な記号であり、通常の「=」の使用とは異なり、対称関係ではありません。したがって、例えばn ^{O (1)} = O ( e ⁿ )は、誤った命題O ( e ⁿ ) = n ^{O (1)}を意味しません。 ${\displaystyle n\to \infty }$$${\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}}}$$

ビッグオーは、次の例のように、斜体大文字の「O」としてタイプセットされます。^{[12] [13]} TeX では、数式モードでOと入力するだけで生成されます。ギリシャ語でバッハマン・ランダウ記法と呼ばれる表記法とは異なり、特別な記号は必要ありません。ただし、一部の著者は代わりにカリグラフィの変種を使用しています。^{[14] [15]}${\displaystyle O(n^{2})}$${\displaystyle {\mathcal {O}}}$

以下は、アルゴリズムの実行時間を分析するときによく遭遇する関数のクラスのリストです。いずれの場合も、c は正の定数で、n は無制限に増加します。一般的に、増加が遅い関数が最初にリストされます。

このステートメントは、漸近的複雑さのより単純な式を導くために、 に弱められることがあります。任意の および に対して、は任意の に対してのサブセットであるため、はより大きな次数を持つ多項式と見なすことができます。 ${\displaystyle f(n)=O(n!)}$${\displaystyle f(n)=O\left(n^{n}\right)}$${\displaystyle k>0}$${\displaystyle c>0}$ ${\displaystyle O(n^{c}(\log n)^{k})}$${\displaystyle O(n^{c+\varepsilon })}$${\displaystyle \varepsilon >0}$

Big Oはコンピュータサイエンスで広く使用されています。他の関連する表記法とともに、バッハマン-ランダウ表記法のファミリーを形成します。^{[引用が必要]}

直感的には、「 f ( x )はo ( g ( x ))である」という主張（「f ( x )はg ( x )の o より小さい」または「f ( x )はg ( x )より劣る」と読む）は、g ( x ) がf ( x )よりはるかに速く増加する、または同等に、f ( x ) がg ( x )よりはるかに遅く増加することを意味します。前と同様に、f を実数値または複素数値関数、g を実数値関数とし、両方とも正の実数の無制限のサブセット上で定義され、 xの十分に大きい値すべてに対してg ( x ) が厳密に正であるとします。次のように書きます。

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

あらゆる正 の定数εに対して、${\displaystyle x_{0}}$

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

例えば、

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

ビッグオー記法の定義とリトルオー記法の定義の違いは、前者は少なくとも1つの定数Mに対して成り立つ必要があるのに対し、後者はどんなに小さくてもすべての正の定数ε^{に対して成り立つ必要があることです。 [17]}このように、リトルオー記法は対応するビッグオー記法よりも強い主張をします。つまり、 gのリトルオーであるすべての関数はgのビッグオーでもありますが、 gのビッグオーであるすべての関数がgのリトルオーであるとは限りません。たとえば、しかし。${\displaystyle 2x^{2}=O(x^{2})}$${\displaystyle 2x^{2}\neq o(x^{2})}$

g ( x ) がゼロでない場合、または少なくともある点を超えるとゼロでなくなる場合、関係式は次の式と等しくなります。 ${\displaystyle f(x)=o(g(x))}$

${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0}$（実際、これはLandau ^[16]が元々little-o表記を定義した方法です）。

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

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(g)}$${\displaystyle g=o(h)}$${\displaystyle f=o(h).}$

もう一つの漸近的記法は であり、「ビッグオメガ」と読む。^[18]この命題には2つの広く普及した、矛盾する定義がある。 ${\displaystyle \Omega }$

${\displaystyle f(x)=\Omega (g(x))}$として、${\displaystyle x\to a}$

ここで、aは実数、、または であり、fとg はaの近傍で定義された実関数であり、g はこの近傍で正です。 ${\displaystyle \infty }$${\displaystyle -\infty }$

ハーディ・リトルウッドの定義は主に解析的数論で使用され、クヌースの定義は主に計算複雑性理論で使用されますが、これらの定義は同等ではありません。

1914年にGHハーディとJEリトルウッドは次のように定義される新しい記号^[19]を導入しました。 ${\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つの新しい記号を導入し、次のように定義した。^[20]${\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. Landauによって同じ意味で使用されました。 ^[21] Landauに続く著者は、同じ定義に対して異なる表記法を使用しています。^[要出典]この記号は、同じ定義を持つ現在の表記法に置き換えられ、${\displaystyle \ \Omega _{R}\ }$${\displaystyle \ \Omega _{+}\ }$${\displaystyle \ \Omega _{L}\ }$${\displaystyle \ \Omega _{-}~.}$

これら3つの記号と（とが両方とも満たされることを意味する）は、現在では解析的整数論で使用されている。^{[22] [23]}${\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 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 ~.}$

1976年にドナルド・クヌースは、より強い特性を表すために - 記号を使用することを正当化する論文を発表しました。 ^[24]クヌースは次のように書いています。「私がこれまでコンピュータサイエンスで見てきたすべてのアプリケーションでは、より強い要件の方がはるかに適切です」。彼は次のように定義しました。 ${\displaystyle \Omega }$

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

コメント：「私はハーディとリトルウッドの の定義を変更しましたが、彼らの定義が広く使用されているわけではなく、彼らの定義が適用される比較的まれなケースでは、彼らが言いたいことを他の方法で表現できるため、変更することは正当だと感じています。」^[24]${\displaystyle \Omega }$

極限定義では、十分に大きい に対して を仮定しています。表は、関数 上の(のクヌース版) が実数直線上のに対応するという意味で、(部分的に) 最小から最大の順に並べられています^[27] (ただし、 のハーディ–リトルウッド版は、そのような記述のいずれにも対応していません)。 ${\displaystyle g(n)>0}$${\displaystyle n}$${\displaystyle o,O,\Theta ,\sim ,}$${\displaystyle \Omega ,\omega }$${\displaystyle <,\leq ,\approx ,=,}$${\displaystyle \geq ,>}$${\displaystyle \Omega }$

コンピュータサイエンスでは、大、大シータ、小、小オメガ、クヌースの大オメガ表記法が用いられる。^[28]解析的数論では、大、小、ハーディの、^[29]ハーディ・リトルウッドの大オメガ（+、-、±の添え字の有無にかかわらず）表記法がよく用いられる。^[22]小オメガ表記法は解析学ではそれほど頻繁には用いられない。^[30]${\displaystyle O}$${\displaystyle \Theta }$${\displaystyle o}$${\displaystyle \omega }$${\displaystyle \Omega }$${\displaystyle O}$${\displaystyle o}$${\displaystyle \asymp }$${\displaystyle \Omega }$${\displaystyle \sim }$${\displaystyle \omega }$

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

1. T ( n ) = O ( n ¹⁰⁰ )
2. T ( n ) = O ( n ³ )
3. T ( n ) = Θ( n ³ )

同等の英語の文はそれぞれ次のようになります。

1. T ( n ) は漸近的にn ¹⁰⁰より速く増加しない
2. T ( n ) は漸近的にn ³より速く増加しない
3. T ( n )はn3と同じ速さで漸近的に増加し^ます。

したがって、3 つの記述はすべて正しいものの、それぞれに含まれる情報は徐々に増えていきます。ただし、分野によっては、大きな O 表記 (上記のリストの 2 番目) の方が、大きな Theta 表記 (上記のリストの 3 番目の項目) よりも一般的に使用されます。たとえば、T ( n ) が入力サイズnに対して新しく開発されたアルゴリズムの実行時間を表す場合、アルゴリズムの発明者とユーザーは、下限漸近境界について明示的に記述せずに、実行にかかる時間の上限漸近境界を設定する傾向があります。

コーメン、レイザーソン、リベスト、スタインは、著書『アルゴリズム入門』の中で、次を満たす 関数fの集合を考察している。

${\displaystyle f(n)=O(g(n))\quad (n\to \infty )~.}$

正しい表記では、この集合は例えばO ( g )と呼ばれる。ここで

$${\displaystyle O(g)=\{f:{\text{there exist positive constants}}~c~{\text{and}}~n_{0}~{\text{such that}}~0\leq f(n)\leq cg(n){\text{ for all }}n\geq n_{0}\}.}$$^[32]

著者らは、集合の所属を表すのに集合の所属演算子 (∈) ではなく等号演算子 (=) を使用するのは表記法の乱用だが、そうすることには利点もあると述べている。^{[6]方程式や不等式の中で漸近表記法を使用すると、集合}O ( g )内の無名関数を表し、低次の項が排除され、方程式の不要な混乱を減らすのに役立つ。例えば、次のようになる。^[33]

${\displaystyle 2n^{2}+3n+1=2n^{2}+O(n).}$

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

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

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

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

任意のノルムベクトル空間で値を取る関数への一般化は簡単である（絶対値をノルムに置き換える）。ここで、fとg は同じ空間で値を取る必要はない。任意の位相群で値を取る関数gへの一般化も可能である^{[引用が必要]}。「極限過程」x → x _oは、任意のフィルタ基数を導入することによって、つまり有向ネットfと gに一般化することもできる。o表記法は、非常に一般的な空間での導関数と微分可能性、および関数の（漸近的）同値性を 定義するために使用できる。

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

これは同値関係であり、上記の「 fは Θ( g )」という関係よりも制限的な概念です。( fとg が正の実数値関数の場合、 lim f / g = 1になります。) たとえば、 2 xは Θ( x ) ですが、2 x − xはo ( x )ではありません。

記号 O は、数論学者ポール・バッハマンが1894 年に著書Analytische Zahlentheorie (解析数論) の第 2 巻で初めて導入しました。^[1]数論学者エドモンド・ランダウがこれを採用し、1909 年に o という表記法を導入しました。^[2]そのため、現在では両方ともランダウ記号と呼ばれています。これらの表記法は、1950 年代に応用数学で漸近解析に使用されました。^[36] 記号(「のoではない」という意味) は、1914 年にハーディとリトルウッドによって導入されました。^[19]ハーディとリトルウッドは、1916 年に(「右」) と(「左」) という記号も導入しました。^[20] これらは、現代の記号(「の小さな o より小さくない」と(「の小さな o より大きくない」) の前身です。したがって、オメガ記号 (本来の意味) は「ランダウ記号」と呼ばれることもあります。この表記法は少なくとも1950年代以降、数論で一般的に使われるようになった。^[37]${\displaystyle \Omega }$${\displaystyle \Omega _{R}}$${\displaystyle \Omega _{L}}$${\displaystyle \Omega _{+}}$${\displaystyle \Omega _{-}}$${\displaystyle \Omega }$

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

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

ハーディが作った他の2つの記号は（現代のO表記法で言えば）

${\displaystyle f\preccurlyeq g\iff f=O(g)}$   そして   ${\displaystyle f\prec g\iff f=o(g);}$

(しかしハーディは、時々報告されているように、 や という表記法を定義したり使用したりしたことはありません)。ハーディは、記号および(およびすでに述べた他の記号) を 1910 年の小冊子「無限大の秩序」で導入し、3 つの論文 (1910 ～ 1913 年) でのみ使用しました。残りの 400 近くの論文と本では、一貫してランダウ記号 O と o を使用しました。 ${\displaystyle \prec \!\!\prec }$${\displaystyle \ll }$${\displaystyle \preccurlyeq }$${\displaystyle \prec }$

ハーディの記号と（および）は、現在では使われていない。一方、1930年代に^[41]ロシアの数論学者 イヴァン・マトヴェイエヴィチ・ヴィノグラードフが という表記法を導入し 、数論では という表記法に代わって使用されるようになった。 ${\displaystyle \preccurlyeq }$${\displaystyle \prec }$${\displaystyle \,\asymp \!\!\!\!\!\!-}$${\displaystyle \ll }$${\displaystyle O}$

${\displaystyle f\ll g\iff f=O(g),}$

そして、同じ論文の中で両方の表記法が使用されることもよくあります。

ビッグオーはもともと「秩序」（「Ordnung」、バッハマン 1894）を意味し、ラテン文字である。バッハマンもランドーもこれを「オミクロン」と呼ぶことはない。この記号はずっと後になって（1976年）、クヌースによって大文字のオミクロンとみなされたが、^{[24]おそらく彼の記号}オメガの定義に関連していると思われる。数字のゼロは使用すべきではない。

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

• ハーディ、GH（1910）。無限の秩序：ポール・デュ・ボワ＝レーモンの「無限計算」。ケンブリッジ大学出版局。
• Knuth, Donald (1997)。「1.2.11: 漸近的表現」。基本アルゴリズム。コンピュータプログラミングの技法。第 1 巻 (第 3 版)。Addison- Wesley。ISBN 978-0-201-89683-1。
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001)。「3.1: 漸近記法」アルゴリズム入門(第 2 版)。MIT Press および McGraw- Hill。ISBN 978-0-262-03293-3。
• シプサー、マイケル(1997)。計算理論入門。PWS 出版。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 日閲覧。
• Black, Paul E. (2004 年 12 月 17 日)。Black, Paul 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記法 – 何に役立つのか
• 第一微分の中心差分法の精度におけるビッグオーの例 2018-10-07 にWayback Machineでアーカイブされました
• アルゴリズムの複雑性分析へのやさしい入門