Describes approximate behavior of a function
ビッグオー 記法 は、 定義域 における 関数 のおおよその大きさを記述する 数学表記法 である 。ビッグオー記法は、ドイツの数学者 パウル・バッハマン [1] と エドムンド・ランダウ [2] によって考案
され、他の人々によって拡張された一連の記法の一つであり、総称して バッハマン・ランダウ記法 と呼ばれる。文字Oは、バッハマンによって 近似の順序 を意味する Ordnung を表すために選ばれた。
コンピュータサイエンス では 、ビッグオー記法は、 入力サイズの増加に応じて 実行時間やメモリ容量の要件がどのように増加するかによって アルゴリズムを分類するために使用されます。 [a] [3] 解析数論
では 、ビッグオー記法は 算術関数の増加に対する境界を表現するためによく使用されます。よく知られた例の 1 つは 素数定理 の剰余項です 。 [4] 微積分 を含む 数学的解析 では、ビッグオー記法は、 べき級数 を切り捨てるときに誤差を制限したり 、実数値または複素数値関数をより単純な関数で近似する品質を表現するために使用されます。
多くの場合、ビッグオー記法は、変数が大きくなるにつれて関数の成長率に基づいて関数を特徴づけます。つまり、同じ漸近的成長率を持つ異なる関数は、同じオー記法で表すことができます。関数の成長率は 関数の位数 とも呼ばれるため、文字「オー」が使われます。ビッグオー記法による関数の記述は、 関数の成長率の 上限のみを示します。
ビッグO表記法には、、、、、、、、 など の 記号を使用して成長率の他の種類の境界を記述するいくつかの関連表記法があります 。 [ 5 ] [ 6] [7 ] o {\displaystyle o} ∼ {\displaystyle \sim } Ω {\displaystyle \Omega } ≪ {\displaystyle \ll } ≫ {\displaystyle \gg } ≍ {\displaystyle \asymp } ω {\displaystyle \omega } Θ {\displaystyle \Theta }
推定対象となる関数 を定義 域上で定義された 実 数値または 複素数 値関数と し 、 比較関数 を同じ集合 上で定義された非負の実数値関数とします 。定義域 の一般的な選択肢としては、有界または非有界の実数区間、正の整数の集合、 複素数 の集合、実数と複素数の組などがあります。定義域 を明示的に記述するか暗黙的に理解する場合、
と なる正の実数が存在するとき、 と書き、「 は のビッグオーである」 と読みます。定義 域 全体 にわたって、 が 有界関数 である という 定義は同等です 。この定義は、定義域が有限、無限、実数、複素数、一変数、多変数の場合を含む、コンピュータサイエンスと数学におけるビッグオーのあらゆる用法を網羅しています。ほとんどのアプリケーションでは、 内に現れる関数 は通常、定数因子と低次の項を省略し、可能な限り単純なものが選択されます。この数は 暗黙定数 と呼ばれます 。ビッグオー記法を使用する場合、重要なのは が 存在することであり、特定の値ではありません。これにより、多くの解析的不等式の表現が簡素化されます。 f , {\displaystyle f,} D {\displaystyle D} g , {\displaystyle g,} D {\displaystyle D} f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O{\bigl (}g(x){\bigr )}} f ( x ) {\displaystyle f(x)} g ( x ) {\displaystyle g(x)} M {\displaystyle M} | f ( x ) | ≤ M g ( x ) for all x ∈ D . {\displaystyle |f(x)|\leq M\ g(x)\quad {\text{ for all }}x\in D~.} g ( x ) > 0 {\displaystyle g(x)>0} D {\displaystyle D} f ( x ) / g ( x ) {\displaystyle f(x)/g(x)} g ( x ) {\displaystyle g(x)} O ( ⋅ ) {\displaystyle O(\cdot )} M {\displaystyle M} M {\displaystyle M}
正の実数または正の整数で定義された関数については、より限定的で多少矛盾する定義が、特にコンピュータサイエンスの分野では今でも一般的に用いられています [3]
、 [8] 。 最終的に 正となる関数に限定された場合 、この表記は
、 ある実数 に対して 、
定義 域 が成り立つことを意味します 。ここで、この式は 極限 を 示すのでは なく、十分に大きな に対して不等式が成り立つという概念を示しています 。多くの場合 [3]、 この式 は省略されます。 f ( x ) = O ( g ( x ) ) as x → ∞ {\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to \infty } a {\displaystyle a} f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))} [ a , ∞ ) {\displaystyle [a,\infty )} x → ∞ {\displaystyle x\to \infty } x {\displaystyle x} x → ∞ {\displaystyle x\to \infty }
同様に、有限実数 に対して 、 という表記は
、 区間 上 、 つまり の小さな近傍において、 ある定数 に対して が成り立つことを意味します 。さらに、 という表記は
が成り立つ ことを意味します 。より複雑な表現も可能です。 a {\displaystyle a} f ( x ) = O ( g ( x ) ) as x → a {\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}\ x\to a} c > 0 {\displaystyle c>0} f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))} [ c − a , c + a ] {\displaystyle [c-a,c+a]} a {\displaystyle a} f ( x ) = h ( x ) + O ( g ( x ) ) {\displaystyle f(x)=h(x)+O(g(x))} f ( x ) − h ( x ) = O ( g ( x ) ) {\displaystyle f(x)-h(x)=O(g(x))}
表記法では等号が使用されていますが、
は方程式ではなく、 と を関連付ける不等式を指します 。 f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))} f {\displaystyle f} g {\displaystyle g}
1930年代 [6] にロシアの数論学者 イヴァン・マトヴェイヴィチ・ヴィノグラードフが という記法を導入し 、これは という記法 の代替として 数論でますます使われるようになった [4] [9] [10] 。 ≪ {\displaystyle \ll } O {\displaystyle O}
f ≪ g ⟺ f = O ( g ) , {\displaystyle f\ll g\iff f=O(g),} そして、同じ論文の中で両方の表記法が使用されることもよくあります。
ビッグOのセットバージョン コンピュータサイエンス [3]では、big Oを 集合 として定義することも一般的です。正の整数上に定義された正の（あるいは最終的には正となる）関数の限定されたクラス内では、 を満たす すべての関数の 集合 に対して と 書きます 。そして と書くことができます 。 O ( g ( x ) ) {\displaystyle O(g(x))} f {\displaystyle f} f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))} f ( x ) ∈ O ( g ( x ) ) {\displaystyle f(x)\in O(g(x))}
無限領域の例 典型的な用法では、この 表記法は実数の無限区間に適用され 、非常に大きな に対する関数の挙動を捉えます 。この設定では、「最も急速に」増加する項の寄与が、最終的に他の項を無関係にします。結果として、以下の簡略化規則を適用できます。 O {\displaystyle O} [ a , ∞ ) {\displaystyle [a,\infty )} x {\displaystyle x}
複数の項の合計である場合 、成長率が最も大きい項があればそれを保持し、その他すべてを省略することができます。 f ( x ) {\displaystyle f(x)} が複数の因数の積である場合 、定数（ に依存しない積の因数 ）は省略できます。 f ( x ) {\displaystyle f(x)} x {\displaystyle x} 例えば、 とし 、表記法を使用してこの関数を簡略化し、 が大きい場合の成長率を記述するとします。この関数は 、、、 および の 3 つの項の和です。これらの 3 つの項のうち、成長率が最も高い項は 、 の関数として最大の指数を持つ項、つまり です 。ここで 2 番目の規則を適用できます。は と の積であり 、最初の因子は に依存しません 。この因子を省略すると、簡略化された形式 になります。したがって、 は の「ビッグ O」である と言えます 。数学的には、 すべての に対して と書くことができます 。この計算は、正式な定義を使用して確認できます。および とします 。上記の正式な定義を適用すると、 というステートメントは、 適切に選択した正の実数に対して、 すべての に対して という 展開
と同等 です。これを証明するには、 とします 。すると、すべての に対して となります 。 したがって 、 と同じ議論により、 であることも成り立ちますが 、これは関数 の精度の低い近似です 。一方、この文は 誤りです。なぜなら、この項は 無制限になる から
です。 f ( x ) = 6 x 4 − 2 x 3 + 5 {\displaystyle f(x)=6x^{4}-2x^{3}+5} O {\displaystyle O} x {\displaystyle x} 6 x 4 {\displaystyle 6x^{4}} − 2 x 3 {\displaystyle -2x^{3}} 5 {\displaystyle 5} x {\displaystyle x} 6 x 4 {\displaystyle 6x^{4}} 6 x 4 {\displaystyle 6x^{4}} 6 {\displaystyle 6} x 4 {\displaystyle x^{4}} x {\displaystyle x} x 4 {\displaystyle x^{4}} f ( x ) {\displaystyle f(x)} x 4 {\displaystyle x^{4}} f ( x ) = O ( x 4 ) {\displaystyle f(x)=O(x^{4})} x ≥ 1 {\displaystyle x\geq 1} f ( x ) = 6 x 4 − 2 x 3 + 5 {\displaystyle f(x)=6x^{4}-2x^{3}+5} g ( x ) = x 4 {\displaystyle g(x)=x^{4}} f ( x ) = O ( x 4 ) {\displaystyle f(x)=O(x^{4})} | f ( x ) | ≤ M x 4 {\displaystyle |f(x)|\leq Mx^{4}} M {\displaystyle M} x ≥ 1 {\displaystyle x\geq 1} M = 13 {\displaystyle M=13} x ≥ 1 {\displaystyle x\geq 1} | 6 x 4 − 2 x 3 + 5 | ≤ 6 x 4 + | − 2 x 3 | + 5 ≤ 6 x 4 + 2 x 4 + 5 x 4 = 13 x 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}}} | 6 x 4 − 2 x 3 + 5 | ≤ 13 x 4 . {\displaystyle |6x^{4}-2x^{3}+5|\leq 13x^{4}.} f ( x ) = O ( x 10 ) {\displaystyle f(x)=O(x^{10})} f {\displaystyle f} f ( x ) = O ( x 3 ) {\displaystyle f(x)=O(x^{3})} 6 x 4 {\displaystyle 6x^{4}} f ( x ) / x 3 {\displaystyle f(x)/x^{3}}
関数 が入力 を持つアルゴリズムに必要なステップ数を記述する場合 、暗黙のドメインが正の整数の集合である のような式は 、アルゴリズムの時間計算量 が最大で のオーダー であると解釈できます。 T ( n ) {\displaystyle T(n)} n {\displaystyle n} T ( n ) = O ( n 2 ) {\displaystyle T(n)=O(n^{2})} n 2 {\displaystyle n^{2}}
有限領域の例 Big O は、有限区間における数学関数の近似における 誤差項 を記述するためにも使用できます。最も重要な項は明示的に記述され、最も重要でない項は単一の Big O 項にまとめられます。例えば、 指数級数 と、が小さい 場合に有効な2つの式を考えてみましょう。 中央の式 （ 「 」 の行 ） は、 が小さい場合、 誤差の絶対値 が最大で定数倍であることを意味します。これは テイラーの定理 の使用例です 。 x {\displaystyle x} e x = 1 + x + x 2 2 ! + x 3 3 ! + x 4 4 ! + ⋯ for all finite x = 1 + x + x 2 2 + O ( | x | 3 ) for all | x | ≤ 1 = 1 + x + O ( x 2 ) for all | x | ≤ 1. {\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}}} O ( | x 3 | ) {\displaystyle O(|x^{3}|)} e x − ( 1 + x + x 2 2 ) {\displaystyle \ e^{x}-(1+x+{\frac {\;x^{2}\ }{2}})\ } | x 3 | {\displaystyle ~|x^{3}|\ } x {\displaystyle \ x~}
与えられた関数の挙動は有限領域と無限領域で大きく異なる可能性がある。例えば 、 ( x + 1 ) 8 = x 8 + O ( x 7 ) for x ≥ 1 {\displaystyle (x+1)^{8}=x^{8}+O(x^{7})\quad {\text{ for }}x\geq 1} ( x + 1 ) 8 = 1 + 8 x + O ( x 2 ) for | x | ≤ 1. {\displaystyle (x+1)^{8}=1+8x+O(x^{2})\quad {\text{ for }}|x|\leq 1.}
多変量の例 x sin y = O ( x ) for x ≥ 1 , y any real number {\displaystyle x\sin y=O(x)\quad {\text{ for }}x\geq 1,y{\text{ any real number}}}
3 a 2 + 7 a b + 2 b 2 + a + 3 b + 14 ≪ a 2 + b 2 ≪ a 2 for all a ≥ b ≥ 1 {\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}
x y x 2 + y 2 = O ( 1 ) for all real x , y that are not both 0 {\displaystyle {\frac {xy}{x^{2}+y^{2}}}=O(1)\quad {\text{ for all real }}x,y{\text{ that are not both }}0}
x i t = O ( 1 ) for x ≠ 0 , t ∈ R . {\displaystyle x^{it}=O(1)\quad {\text{ for }}x\neq 0,t\in \mathbb {R} .}
ここでは2変数の 複素変数 関数を扱っています。一般に、有界関数は です 。 O ( 1 ) {\displaystyle O(1)}
( x + y ) 10 = O ( x 10 ) for x ≥ 1 , − 2 ≤ y ≤ 2. {\displaystyle (x+y)^{10}=O(x^{10})\quad {\text{ for }}x\geq 1,-2\leq y\leq 2.}
最後の例は、さまざまな変数における有限領域と無限領域の混合を示しています。
これらの例において、境界は両変数において一様です。多変数式では、ある変数が他の変数よりも重要になる場合があり、その場合は、 大文字のO記号または記号の添え字を用いて、暗黙の定数が1つ以上の変数に依存することを表現できます 。例えば、次の式を考えてみましょう。 M {\displaystyle M} ≪ {\displaystyle \ll }
( 1 + x ) b = 1 + O b ( x ) for 0 ≤ x ≤ 1 , b any real number. {\displaystyle (1+x)^{b}=1+O_{b}(x)\quad {\text{ for }}0\leq x\leq 1,b{\text{ any real number.}}}
これは、各実数に対して、 に依存する定数 が存在することを意味します。 その ため 、 すべての に対して 、 この特定の記述は 一般二項定理 から得られます。 b {\displaystyle b} M b {\displaystyle M_{b}} b {\displaystyle b} 0 ≤ x ≤ 1 {\displaystyle 0\leq x\leq 1} | ( 1 + x ) b − 1 | ≤ M b ⋅ x . {\displaystyle |(1+x)^{b}-1|\leq M_{b}\cdot x.}
テイラー級数 の理論でよく見られる別の例は、次のとおり です。 ここで、暗黙の定数はドメインのサイズに依存します。 e x = 1 + x + O r ( x 2 ) for all | x | ≤ r , r being any real number. {\displaystyle e^{x}=1+x+O_{r}(x^{2})\quad {\text{ for all }}|x|\leq r,r{\text{ being any real number.}}}
下付き文字の規則はこのページの他のすべての表記に適用されます。
プロパティ
製品 f 1 = O ( g 1 ) and f 2 = O ( g 2 ) ⇒ f 1 f 2 = O ( g 1 g 2 ) {\displaystyle f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})} f ⋅ O ( g ) = O ( | f | g ) {\displaystyle f\cdot O(g)=O(|f|g)}
和 ならば 。 ならば 。 f 1 = O ( g 1 ) {\displaystyle f_{1}=O(g_{1})} f 2 = O ( g 2 ) {\displaystyle f_{2}=O(g_{2})} f 1 + f 2 = O ( max ( g 1 , g 2 ) ) {\displaystyle f_{1}+f_{2}=O(\max(g_{1},g_{2}))} f 1 = O ( g ) {\displaystyle f_{1}=O(g)} f 2 = O ( g ) {\displaystyle f_{2}=O(g)} f 1 + f 2 = O ( g ) {\displaystyle f_{1}+f_{2}=O(g)}
定数による乗算 kを 非ゼロの定数とします。すると となります 。 言い換えれば、 ならば O ( | k | ⋅ g ) = O ( g ) {\displaystyle O(|k|\cdot g)=O(g)} f = O ( g ) {\displaystyle f=O(g)} k ⋅ f = O ( g ) . {\displaystyle k\cdot f=O(g).}
推移的性質 ならば 、 。 f = O ( g ) {\displaystyle f=O(g)} g = O ( h ) {\displaystyle g=O(h)} f = O ( h ) {\displaystyle f=O(h)}
正の整数の 関数が 他の関数の有限和として表せる場合、最も速く増加する関数が の位数を決定する 。例えば、 f {\displaystyle f} n {\displaystyle n} f ( n ) {\displaystyle f(n)}
f ( n ) = 9 log n + 5 ( log n ) 4 + 3 n 2 + 2 n 3 = O ( n 3 ) for n ≥ 1. {\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 番目の特性は 、ロピタルの規則 を使用して厳密に証明できます 。
大国が小国を支配する の場合 、 b > a ≥ 0 {\displaystyle b>a\geq 0} n a = O ( n b ) . {\displaystyle n^{a}=O(n^{b}).}
対数はべき乗が支配的である 任意の正の に対して、 がどれだけ 大きく ても がどれだけ小さくても
関係ありません 。ここで、暗黙の定数は と の両方に依存し ます 。 a , b , {\displaystyle a,b,} ( log n ) a = O a , b ( n b ) , {\displaystyle (\log n)^{a}=O_{a,b}(n^{b}),} a {\displaystyle a} b {\displaystyle b} a {\displaystyle a} b {\displaystyle b}
指数関数は累乗を支配する どんなに大きくて も小さくて
も、 どんなにポジティブなものでも 。 a , b , {\displaystyle a,b,} n a = O a , b ( e b n ) , {\displaystyle n^{a}=O_{a,b}(e^{bn}),} a {\displaystyle a} b {\displaystyle b}
任意の に対して よりも速く増加する関数は、 超多項式 と呼ばれます 。 の形の任意の指数関数よりも遅く増加する関数は、 劣指数関数 と呼ばれます。アルゴリズム によっては、超多項式かつ劣指数関数的な時間を必要とする場合があります。このような例としては、 整数因数分解 の既知の最速アルゴリズム や関数 などがあります 。 n c {\displaystyle n^{c}} c {\displaystyle c} c n {\displaystyle c^{n}} c > 1 {\displaystyle c>1} n log n {\displaystyle n^{\log n}}
対数の内部における のべき乗は無視できます。 が正の数である場合 、 の表記は と全く同じ意味になります 。なぜなら だからです 。同様に、異なる定数の底を持つ対数は、Big O表記に関して等価です。一方、異なる底を持つ指数関数は同じ位数ではありません。例えば、 と は 同じ位数ではありません。 n {\displaystyle n} c {\displaystyle c} O ( log n ) {\displaystyle O(\log n)} O ( log ( n c ) ) {\displaystyle O(\log(n^{c}))} log ( n c ) = c log n {\displaystyle \log(n^{c})=c\log n} 2 n {\displaystyle 2^{n}} 3 n {\displaystyle 3^{n}}
より複雑な表現 より複雑な用法では、 は方程式の異なる場所に出現し、各辺に複数回出現することもあります。例えば、 正の整数について以下が成り立ちます。 これらの文の意味は次のとおりです。 左辺で それぞれ を満たす任意の関数 に対して 、右辺で それぞれ を満たす関数 がいくつか 存在し、これらの関数すべてを方程式に代入すると両辺が等しくなります。例えば、上記の3番目の方程式は、「 を満たす任意の関数に対して、となる 関数が存在する 」という意味です。文「 」に含まれる暗黙の定数は、 式「 」に含まれる暗黙の定数に依存する場合があります 。 O ( ⋅ ) {\displaystyle O(\cdot )} n {\displaystyle n} ( 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 ) . {\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 ( ⋅ ) {\displaystyle O(\cdot )} O ( ⋅ ) {\displaystyle O(\cdot )} f ( n ) = O ( 1 ) {\displaystyle f(n)=O(1)} g ( n ) = O ( e n ) {\displaystyle g(n)=O(e^{n})} n f ( n ) = g ( n ) {\displaystyle n^{f(n)}=g(n)} g ( n ) = O ( e n ) {\displaystyle g(n)=O(e^{n})} f ( n ) = O ( 1 ) {\displaystyle f(n)=O(1)}
さらにいくつかの例: f = O ( g ) ⇒ ∫ a b f = O ( ∫ a b g ) f ( x ) = g ( x ) + O ( 1 ) ⇒ e f ( x ) = O ( e g ( x ) ) ( 1 + O ( 1 / x ) ) O ( x ) = O ( 1 ) for x > 0 sin x = O ( | x | ) for all real x . {\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つの表記は視覚的に対称性があり、正関数 については 、 f , g {\displaystyle f,g} f ( x ) ≫ g ( x ) {\displaystyle f(x)\gg g(x)} g ( x ) = O ( f ( x ) ) {\displaystyle g(x)=O(f(x))} f , g {\displaystyle f,g} f ( x ) ≪ g ( x ) ⟺ g ( x ) ≫ f ( x ) . {\displaystyle f(x)\ll g(x)\Longleftrightarrow g(x)\gg f(x).}
1976年に ドナルド・クヌース [7] は
f ( x ) = Ω ( g ( x ) ) ⟺ g ( x ) = O ( f ( x ) ) {\displaystyle f(x)=\Omega (g(x))\Longleftrightarrow g(x)=O(f(x))} これは、Vinogradov の と同じ意味です 。 f ( x ) ≫ g ( x ) {\displaystyle f(x)\gg g(x)}
はるか以前、ハーディとリトルウッドは 異なる定義をしていましたが、これは現在ではほとんど使われていません（イヴィッチの著書 [9] は例外です）。 より強い性質を表すために記号-を使用したことを正当化するために、クヌースは [7] 次のように書いています。「私がこれまでコンピュータサイエンスの分野で見てきたすべての応用において、より強い要件…の方がはるかに適切です。」クヌースはさらに、「私はハーディとリトルウッドの の定義を変更しましたが 、彼らの定義が広く使われているわけではなく、彼らの定義が適用される比較的まれなケースでは、彼らが言いたいことを他の方法で表現できるため、変更しても正当だと感じています。」 [7] Ω {\displaystyle \Omega } Ω {\displaystyle \Omega } Ω {\displaystyle \Omega }
実際、クヌースのビッグは 、コンピューターサイエンスと組み合わせ論の一般的な特徴であるため、 ハーディ–リトルウッドのビッグよりもはるかに広く使用されています。 Ω {\displaystyle \Omega } Ω {\displaystyle \Omega }
ハーディの≍とクヌースの大きなΘ 解析的数論において、 [10] という表記は と の 両方を意味する 。この表記はもともとハーディによるものである。 [5] クヌースは同じ概念を という表記で表した 。 [7] 大まかに言えば、これらの文は と が 同じ位 数を持つことを主張している。これらの表記は 、 の共通定義域内の すべての に対して となる 正の定数が存在することを意味する 。関数が正の整数または正の実数に対して (big O の場合のように) 定義されている場合、筆者はしばしば および の文が十分に大きいすべての に対して、つまりある点 を超えるすべての に対して成り立つと解釈する 。 これ は 、文に を 付記することで示されることがある 。たとえば、
は 定義域に対して真である が、定義域がすべて正の整数の場合は で関数が 0 となるため偽である 。 f ( x ) ≍ g ( x ) {\displaystyle f(x)\asymp g(x)} f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))} g ( x ) = O ( f ( x ) ) {\displaystyle g(x)=O(f(x))} f ( x ) = Θ ( g ( x ) ) {\displaystyle f(x)=\Theta (g(x))} f ( x ) {\displaystyle f(x)} g ( x ) {\displaystyle g(x)} M , N {\displaystyle M,N} N g ( x ) ≤ f ( x ) ≤ M g ( x ) {\displaystyle Ng(x)\leq f(x)\leq Mg(x)} x {\displaystyle x} f , g {\displaystyle f,g} f ( x ) = Ω ( g ( x ) ) {\displaystyle f(x)=\Omega (g(x))} f ( x ) = Θ ( g ( x ) ) {\displaystyle f(x)=\Theta (g(x))} x {\displaystyle x} x {\displaystyle x} x 0 {\displaystyle x_{0}} x → ∞ {\displaystyle x\to \infty } 2 n 2 − 10 n = Θ ( n 2 ) {\displaystyle 2n^{2}-10n=\Theta (n^{2})} n ≥ 6 {\displaystyle n\geq 6} n = 5 {\displaystyle n=5}
その他の例 n 3 + 20 n 2 + n + 12 ≍ n 3 for all n ≥ 1. {\displaystyle n^{3}+20n^{2}+n+12\asymp n^{3}\quad {\text{ for all }}n\geq 1.}
( 1 + x ) 8 = x 8 + Θ ( x 7 ) for all x ≥ 1. {\displaystyle (1+x)^{8}=x^{8}+\Theta (x^{7})\quad {\text{ for all }}x\geq 1.}
表記
f ( n ) = e Ω ( n ) for all n ≥ 1 , {\displaystyle f(n)=e^{\Omega (n)}\quad {\text{ for all }}n\geq 1,} は、すべての に対して となる 正の定数が存在することを意味します 。対照的に、 は、 すべての に対して となる 正の定数が存在することを意味します。 また、 は、 すべての に対して と なる正の定数が存在することを意味します 。 M {\displaystyle M} f ( n ) ≥ e M n {\displaystyle f(n)\geq e^{Mn}} n ≥ 1 {\displaystyle n\geq 1} f ( n ) = e − O ( n ) for all n ≥ 1 , {\displaystyle f(n)=e^{-O(n)}\quad {\text{ for all }}n\geq 1,} M {\displaystyle M} f ( n ) ≥ e − M n {\displaystyle f(n)\geq e^{-Mn}} n ≥ 1 {\displaystyle n\geq 1} f ( n ) = e Θ ( n ) for all n ≥ 1 , {\displaystyle f(n)=e^{\Theta (n)}\quad {\text{ for all }}n\geq 1,} M , N {\displaystyle M,N} e M n ≤ f ( n ) ≤ e N n {\displaystyle e^{Mn}\leq f(n)\leq e^{Nn}} n ≥ 1 {\displaystyle n\geq 1}
任意のドメイン について 、 各文は 内のすべての に対して となります 。 D {\displaystyle D} f ( x ) = g ( x ) + O ( 1 ) ⟺ e f ( x ) ≍ e g ( x ) , {\displaystyle f(x)=g(x)+O(1)\Longleftrightarrow e^{f(x)}\asymp e^{g(x)},} x {\displaystyle x} D {\displaystyle D}
一般的な関数の順序 アルゴリズムの実行時間を分析する際によく遭遇する関数のクラスのリストを以下に示します。いずれの場合も、 c は正の定数であり、 n は 無限に増加します。一般的に、増加速度の遅い関数から順にリストアップされます。
表記 名前 例 O ( 1 ) {\displaystyle O(1)} 絶え間ない ソートされた数値配列の中央値を求める; 計算 ; 一定サイズの ルックアップテーブルを使用する ( − 1 ) n {\displaystyle (-1)^{n}} O ( α ( n ) ) {\displaystyle O(\alpha (n))} 逆アッカーマン関数 分離集合データ構造 における操作ごとの償却複雑度 O ( log log n ) {\displaystyle O(\log \log n)} 二重対数 均一に分布した値のソートされた配列内で 補間検索 を使用して項目を見つけるのに費やされた比較の平均数 O ( log n ) {\displaystyle O(\log n)} 対数 ソートされた配列内の項目を 二分探索 またはバランス探索 木 で探すこと、および 二項ヒープ内のすべての操作 O ( ( log n ) c ) {\displaystyle O((\log n)^{c})} c > 1 {\textstyle c>1} 多重対数 行列連鎖順序付けは、 並列ランダムアクセスマシン 上で多重対数時間で解決できます。 O ( n c ) {\displaystyle O(n^{c})} 0 < c < 1 {\textstyle 0<c<1} 分数乗 kdツリー の検索 O ( n ) {\displaystyle O(n)} リニア ソートされていないリストまたはソートされていない配列内の項目の検索。 リップルキャリー による2つの nビット整数の加算。 O ( n log ∗ n ) {\displaystyle O(n\log ^{*}n)} n ログスター n ザイデルのアルゴリズム [11] を使用して単純な多角形の 三角測量 を実行すると、 log ∗ ( n ) = { 0 , if n ≤ 1 1 + log ∗ ( log n ) , if n > 1 {\displaystyle \log ^{*}(n)={\begin{cases}0,&{\text{if }}n\leq 1\\1+\log ^{*}(\log n),&{\text{if }}n>1\end{cases}}} O ( n log n ) = O ( log n ! ) {\displaystyle O(n\log n)=O(\log n!)} 線形 、対数線形、準線形、または「 」 n log n {\displaystyle n\log n} 高速フーリエ変換の 実行 、可能な限り最速の 比較ソート 、 ヒープソート と マージソート O ( n 2 ) {\displaystyle O(n^{2})} 二次関数 教科書的な掛け算 で2 桁の数字を掛け算する。 バブル ソート 、 選択ソート 、 挿入ソート などの単純なソート アルゴリズム。 クイック ソート 、 シェルソート 、 ツリー ソート などの通常はより高速なソート アルゴリズムの (最悪の場合) 境界。 n {\displaystyle n} O ( n c ) {\displaystyle O(n^{c})} 多項式 または代数式 木結合文法 解析、 二部グラフ の最大 マッチング、 LU分解 による 行列式の 発見 L n [ α , c ] = e ( c + o ( 1 ) ) ( ln n ) α ( ln ln n ) 1 − α {\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}} 0 < α < 1 {\textstyle 0<\alpha <1} L表記 または 指数表記 二次ふるい または 数体ふるい を用いた数の因数分解 O ( c n ) {\displaystyle O(c^{n})} c > 1 {\textstyle c>1} 指数関数 動的計画法 を用いて 巡回セールスマン問題 の（正確な）解を求める； 総当たり探索 を用いて2つの論理文が同等かどうかを判定する O ( n ! ) {\displaystyle O(n!)} 階乗 巡回セールスマン問題を 総当たり探索で 解く； 順序集合 のすべての無制限順列を生成する； ラプラス展開 で 行列式を 求める； 集合のすべての分割を列挙する
この文は、漸近的複雑性に関するより単純な式を導くため に、 と弱められることがあります 。これらの例の多くでは、実行時間は実際には であり 、より正確な表現となっています。 f ( n ) = O ( n ! ) {\displaystyle f(n)=O(n!)} f ( n ) = O ( n n ) {\displaystyle f(n)=O\left(n^{n}\right)} Θ ( g ( n ) ) {\displaystyle \Theta (g(n))}
Little-o 記法 十分に大きい に対して、 実変数の実数値関数または複素数値関数については 、 [ 2]と書くことができる。 x {\displaystyle x} g ( x ) > 0 {\displaystyle g(x)>0} x {\displaystyle x}
f ( x ) = o ( g ( x ) ) as x → ∞ {\displaystyle f(x)=o(g(x))\quad {\text{ as }}x\to \infty } つまり 、すべての正の定数 ε に対して 、 lim x → ∞ f ( x ) g ( x ) = 0. {\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0.} x 0 {\displaystyle x_{0}}
| f ( x ) | ≤ ε g ( x ) for all x ≥ x 0 . {\displaystyle |f(x)|\leq \varepsilon g(x)\quad {\text{ for all }}x\geq x_{0}.} 直感的に言えば、これは が よりもはるかに速く増加する 、あるいは が よりもはるかに遅く増加する
ことを意味します 。例えば、 g ( x ) {\displaystyle g(x)} f ( x ) {\displaystyle f(x)} f ( x ) {\displaystyle f(x)} g ( x ) {\displaystyle g(x)}
200 x = o ( x 2 ) {\displaystyle 200x=o(x^{2})} そして 両方とも 1 / x = o ( 1 ) , {\displaystyle 1/x=o(1),} x → ∞ . {\displaystyle x\to \infty .} の大きな値に対する関数の挙動に興味がある場合 、対応する大 O 表記よりも、小 O 表記の方が 強い表現 になります。つまり、 の小 O である関数はすべて、 ある区間 では の 大 O でもありますが、 の大 O である 関数 すべてが の 小 O であるとは限りません 。たとえば、 の場合 と大 O の場合では、どちらも同じです 。 x {\displaystyle x} g {\displaystyle g} g {\displaystyle g} [ a , ∞ ) {\displaystyle [a,\infty )} g {\displaystyle g} g {\displaystyle g} 2 x 2 = O ( x 2 ) {\displaystyle 2x^{2}=O(x^{2})} 2 x 2 ≠ o ( x 2 ) {\displaystyle 2x^{2}\neq o(x^{2})} x ≥ 1 {\displaystyle x\geq 1}
Little-oはいくつかの算術演算を尊重します。例えば、
が非ゼロの定数である 場合 、 そして c {\displaystyle c} f = o ( g ) {\displaystyle f=o(g)} c ⋅ f = o ( g ) {\displaystyle c\cdot f=o(g)} もし 、 そして f = o ( F ) {\displaystyle f=o(F)} g = o ( G ) {\displaystyle g=o(G)} f ⋅ g = o ( F ⋅ G ) . {\displaystyle f\cdot g=o(F\cdot G).} もし 、 そして f = o ( F ) {\displaystyle f=o(F)} g = o ( G ) {\displaystyle g=o(G)} f + g = o ( F + G ) {\displaystyle f+g=o(F+G)} これは 推移 関係も満たします:
もし 、 そして f = o ( g ) {\displaystyle f=o(g)} g = o ( h ) {\displaystyle g=o(h)} f = o ( h ) . {\displaystyle f=o(h).} Little-o は有限の場合にも一般化できる: [2] if 言い換えれば、
の条件を満たす もの に対してである 。 f ( x ) = o ( g ( x ) ) as x → x 0 {\displaystyle f(x)=o(g(x))\quad {\text{ as }}x\to x_{0}} lim x → x 0 f ( x ) g ( x ) = 0. {\displaystyle \lim _{x\to x_{0}}{\frac {f(x)}{g(x)}}=0.} f ( x ) = α ( x ) g ( x ) {\displaystyle f(x)=\alpha (x)g(x)} α ( x ) {\displaystyle \alpha (x)} lim x → x 0 α ( x ) = 0 {\displaystyle \lim _{x\to x_{0}}\alpha (x)=0}
この定義は、テイラー級数 を用いた 極限 計算において特に有用である 。例えば、
sin x = x − x 3 3 ! + … = x + o ( x 2 ) as x → 0 {\displaystyle \sin x=x-{\frac {x^{3}}{3!}}+\ldots =x+o(x^{2}){\text{ as }}x\to 0} 、 それで lim x → 0 sin x x = lim x → 0 x + o ( x 2 ) x = lim x → 0 1 + o ( x ) = 1 {\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}
漸近記法 litte-o に関連する関係式として、 漸近 記法
があります 。実数値関数 の場合 、式は を 意味します
。 が とも同値である ことに注目することで、これを little-o に結び付けることができます 。ここで は、 がゼロに向かう関数 を指しています。これは「 は に漸近的で ある」 と読みます 。同じ（有限または無限）領域上の非ゼロ関数の場合、は 同値関係 を形成します 。 ∼ {\displaystyle \sim } f , g {\displaystyle f,g} f ( x ) ∼ g ( x ) as x → ∞ {\displaystyle f(x)\sim g(x)\quad {\text{ as }}x\to \infty } lim x → ∞ f ( x ) g ( x ) = 1. {\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=1.} f ( x ) ∼ g ( x ) {\displaystyle f(x)\sim g(x)} f ( x ) = ( 1 + o ( 1 ) ) g ( x ) {\displaystyle f(x)=(1+o(1))g(x)} o ( 1 ) {\displaystyle o(1)} x → ∞ {\displaystyle x\to \infty } f ( x ) {\displaystyle f(x)} g ( x ) {\displaystyle g(x)} ∼ {\displaystyle \sim }
表記法を使用する最も有名な定理の 1 つは
、 スターリングの公式 です。 数論では、有名な 素数定理は 、最大で である素数の個数であり 、 の 自然 対数 である と述べています 。 ∼ {\displaystyle \sim } n ! ∼ ( n e ) n 2 π n as n → ∞ . {\displaystyle n!\sim {\bigg (}{\frac {n}{e}}{\bigg )}^{n}{\sqrt {2\pi n}}\quad {\text{ as }}n\to \infty .} π ( x ) ∼ x log x as x → ∞ , {\displaystyle \pi (x)\sim {\frac {x}{\log x}}\quad {\text{ as }}x\to \infty ,} π ( x ) {\displaystyle \pi (x)} x {\displaystyle x} log {\displaystyle \log } x {\displaystyle x}
little-oと同様に、有限の極限（両側または 片側 ）を持つバージョンもあります。たとえば、 sin x ∼ x as x → 0. {\displaystyle \sin x\sim x\quad {\text{ as }}x\to 0.}
その他の例:
最後の漸近線は リーマンゼータ関数 の基本的な性質です 。 x a = o a , b ( e b x ) as x → ∞ , for any positive constants a , b , {\displaystyle x^{a}=o_{a,b}(e^{bx})\quad {\text{ as }}x\to \infty ,{\text{ for any positive constants }}a,b,} f ( x ) = g ( x ) + o ( 1 ) ⟺ e f ( x ) ∼ e g ( x ) ( x → ∞ ) . {\displaystyle f(x)=g(x)+o(1)\quad \Longleftrightarrow \quad e^{f(x)}\sim e^{g(x)}\quad (x\to \infty ).} ∑ n = 1 ∞ 1 n s ∼ 1 s − 1 ( x → ∞ ) . {\displaystyle \sum _{n=1}^{\infty }{\frac {1}{n^{s}}}\sim {\frac {1}{s-1}}\quad (x\to \infty ).}
クヌースの小さな𝜔 最終的に正の実数値関数の場合、 表記は を意味します
。 言い換えると、 です 。大まかに言えば、 は よりもはるかに速く増大することを意味します 。 f , g , {\displaystyle f,g,} f ( x ) = ω ( g ( x ) ) as x → ∞ {\displaystyle f(x)=\omega (g(x))\quad {\text{ as }}x\to \infty } lim x → ∞ f ( x ) g ( x ) = ∞ . {\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=\infty .} g ( x ) = o ( f ( x ) ) {\displaystyle g(x)=o(f(x))} f ( x ) {\displaystyle f(x)} g ( x ) {\displaystyle g(x)}
ハーディ・リトルウッドΩ表記 1914年に GHハーディ と JEリトルウッドは 次のように定義される 新しい記号 [12]を導入しました。 Ω , {\displaystyle \ \Omega ,}
f ( x ) = Ω ( g ( x ) ) {\displaystyle f(x)=\Omega {\bigl (}\ g(x)\ {\bigr )}\quad } まるで x → ∞ {\displaystyle \quad x\to \infty \quad } lim sup x → ∞ | f ( x ) g ( x ) | > 0 . {\displaystyle \quad \limsup _{x\to \infty }\ \left|{\frac {\ f(x)\ }{g(x)}}\right|>0~.} つまり 、 f ( x ) = Ω ( g ( x ) ) {\displaystyle ~f(x)=\Omega {\bigl (}\ g(x)\ {\bigr )}~} f ( x ) = o ( g ( x ) ) . {\displaystyle ~f(x)=o{\bigl (}\ g(x)\ {\bigr )}~.}
1916年に同じ著者らは2つの新しい記号を導入し 、 次のように定義した。 [13] Ω R {\displaystyle \ \Omega _{R}\ } Ω L , {\displaystyle \ \Omega _{L}\ ,}
f ( x ) = Ω R ( g ( x ) ) {\displaystyle f(x)=\Omega _{R}{\bigl (}\ g(x)\ {\bigr )}\quad } まるで x → ∞ {\displaystyle \quad x\to \infty \quad } lim sup x → ∞ f ( x ) g ( x ) > 0 ; {\displaystyle \quad \limsup _{x\to \infty }\ {\frac {\ f(x)\ }{g(x)}}>0\ ;} f ( x ) = Ω L ( g ( x ) ) {\displaystyle f(x)=\Omega _{L}{\bigl (}\ g(x)\ {\bigr )}\quad } まるで x → ∞ {\displaystyle \quad x\to \infty \quad } lim inf x → ∞ f ( x ) g ( x ) < 0 . {\displaystyle \quad ~\liminf _{x\to \infty }\ {\frac {\ f(x)\ }{g(x)}}<0~.} これらの記号は1924年に E.ランダウ によって同じ意味で使用されました。 [14] しかし、ランダウに続く著者は同じ定義に異なる表記を使用しています。 [9] この記号は同じ定義の 現在の表記に置き換え られ 、 Ω R {\displaystyle \ \Omega _{R}\ } Ω + {\displaystyle \ \Omega _{+}\ } Ω L {\displaystyle \ \Omega _{L}\ } Ω − . {\displaystyle \ \Omega _{-}~.}
これら3つの記号は （ とが両方とも満たされることを意味する） と共に 、現在では 解析的数論 で使用されている。 [9] [10] Ω , Ω + , Ω − , {\displaystyle \ \Omega \ ,\Omega _{+}\ ,\Omega _{-}\ ,} f ( x ) = Ω ± ( g ( x ) ) {\displaystyle \ f(x)=\Omega _{\pm }{\bigl (}\ g(x)\ {\bigr )}\ } f ( x ) = Ω + ( g ( x ) ) {\displaystyle \ f(x)=\Omega _{+}{\bigl (}\ g(x)\ {\bigr )}\ } f ( x ) = Ω − ( g ( x ) ) {\displaystyle \ f(x)=\Omega _{-}{\bigl (}\ g(x)\ {\bigr )}\ }
簡単な例 我々は持っています
sin x = Ω ( 1 ) {\displaystyle \sin x=\Omega (1)\quad } として x → ∞ , {\displaystyle \quad x\to \infty \ ,} そしてより正確には
sin x = Ω ± ( 1 ) {\displaystyle \sin x=\Omega _{\pm }(1)\quad } として x → ∞ , {\displaystyle \quad x\to \infty ,~} ここで、 左辺は と の両方であることを意味し ます 。 Ω ± {\displaystyle \Omega _{\pm }} Ω + ( 1 ) {\displaystyle \Omega _{+}(1)} Ω − ( 1 ) {\displaystyle \Omega _{-}(1)}
我々は持っています
1 + sin x = Ω ( 1 ) {\displaystyle 1+\sin x=\Omega (1)\quad } として x → ∞ , {\displaystyle \quad x\to \infty \ ,} そしてより正確には
1 + sin x = Ω + ( 1 ) {\displaystyle 1+\sin x=\Omega _{+}(1)\quad } として x → ∞ ; {\displaystyle \quad x\to \infty \ ;} しかし
1 + sin x ≠ Ω − ( 1 ) {\displaystyle 1+\sin x\neq \Omega _{-}(1)\quad } として x → ∞ . {\displaystyle \quad x\to \infty ~.}
バッハマン・ランダウ記法の族 正式な定義を理解するには、 数学で使用される 論理記号のリストを参照してください。
表記 名前 [7] 説明 正式な定義 コンパクトな定義 [4] [5] [7] [12] [15] [16]
f ( n ) = o ( g ( n ) ) {\displaystyle f(n)=o(g(n))} 小文字の O; 小文字の Oh; 小文字の O; 小文字の Oh fは漸近的に g に支配される （任意の定数因子に対して ） k {\displaystyle k} ∀ k > 0 ∃ n 0 ∀ n > n 0 : | f ( n ) | ≤ k g ( n ) {\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|\leq k\,g(n)} lim n → ∞ f ( n ) g ( n ) = 0 {\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=0} f ( n ) = O ( g ( n ) ) {\displaystyle f(n)=O(g(n))} または f ( n ) ≪ g ( n ) {\displaystyle f(n)\ll g(n)} （ヴィノグラドフ記法）
ビッグO、ビッグオー、ビッグオミクロン | f | {\displaystyle |f|} はg によって上界となる （定数係数まで ） k {\displaystyle k} ∃ k > 0 ∀ n ∈ D : | f ( n ) | ≤ k g ( n ) {\displaystyle \exists k>0\,\forall n\in D\colon |f(n)|\leq k\,g(n)} sup n ∈ D | f ( n ) | g ( n ) < ∞ {\displaystyle \sup _{n\in D}{\frac {\left|f(n)\right|}{g(n)}}<\infty } f ( n ) ≍ g ( n ) {\displaystyle f(n)\asymp g(n)} （ハーディ記法）または （クヌース記法） f ( n ) = Θ ( g ( n ) ) {\displaystyle f(n)=\Theta (g(n))} （ハーディ）と同じ順序。ビッグシータ（クヌース） fは g によって 上（定数係数 ）と下（定数係数 ）
の両方で制限されます。 k 2 {\displaystyle k_{2}} k 1 {\displaystyle k_{1}} ∃ k 1 > 0 ∃ k 2 > 0 ∀ n ∈ D : {\displaystyle \exists k_{1}>0\,\exists k_{2}>0\,\forall n\in D\colon } k 1 g ( n ) ≤ f ( n ) ≤ k 2 g ( n ) {\displaystyle k_{1}\,g(n)\leq f(n)\leq k_{2}\,g(n)} f ( n ) = O ( g ( n ) ) {\displaystyle f(n)=O(g(n))} そして g ( n ) = O ( f ( n ) ) {\displaystyle g(n)=O(f(n))} f ( n ) ∼ g ( n ) {\displaystyle f(n)\sim g(n)} （ただし 、 は有限） n → a {\displaystyle n\to a} a {\displaystyle a} ∞ {\displaystyle \infty } または − ∞ {\displaystyle -\infty }
漸近的同値性 fは 漸近的に g に等しい ∀ ε > 0 ∃ n 0 ∀ n > n 0 : | f ( n ) g ( n ) − 1 | < ε {\displaystyle \forall \varepsilon >0\,\exists n_{0}\,\forall n>n_{0}\colon \left|{\frac {f(n)}{g(n)}}-1\right|<\varepsilon } （この場合 ） a = ∞ {\displaystyle a=\infty } lim n → a f ( n ) g ( n ) = 1 {\displaystyle \lim _{n\to a}{\frac {f(n)}{g(n)}}=1} f ( n ) = Ω ( g ( n ) ) {\displaystyle f(n)=\Omega (g(n))} （クヌースの記法）、または f ( n ) ≫ g ( n ) {\displaystyle f(n)\gg g(n)} （ヴィノグラドフ記法）
複雑性理論における大きなオメガ（クヌース） f は定数倍まで g によって下界となる ∃ k > 0 ∀ n ∈ D : f ( n ) ≥ k g ( n ) {\displaystyle \exists k>0\,\forall n\in D\colon f(n)\geq k\,g(n)} inf n ∈ D f ( n ) g ( n ) > 0 {\displaystyle \inf _{n\in D}{\frac {f(n)}{g(n)}}>0} f ( n ) = ω ( g ( n ) ) {\displaystyle f(n)=\omega (g(n))} として 、 n → a {\displaystyle n\to a} は 有限である可能性がある、 または a {\displaystyle a} ∞ {\displaystyle \infty } − ∞ {\displaystyle -\infty }
小さなオメガ; 小さなオメガ f は漸近的に g を支配する ∀ k > 0 ∃ n 0 ∀ n > n 0 : f ( n ) > k g ( n ) {\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon f(n)>k\,g(n)} （のために ） a = ∞ {\displaystyle a=\infty } lim n → a f ( n ) g ( n ) = ∞ {\displaystyle \lim _{n\to a}{\frac {f(n)}{g(n)}}=\infty } f ( n ) = Ω ( g ( n ) ) {\displaystyle f(n)=\Omega (g(n))} 数論におけるビッグオメガ（ハーディ・リトルウッド） | f | {\displaystyle |f|} g は漸近的 に支配されない ∃ k > 0 ∀ n 0 ∃ n > n 0 : | f ( n ) | ≥ k g ( n ) {\displaystyle \exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon |f(n)|\geq k\,g(n)} lim sup n → ∞ | f ( n ) | g ( n ) > 0 {\displaystyle \limsup _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}>0}
極限定義では、 極限の近傍で が であると
仮定します。極限が のとき 、これは が 十分に大きい に対して であることを意味します 。 g ( n ) > 0 {\displaystyle g(n)>0} n {\displaystyle n} ∞ {\displaystyle \infty } g ( n ) > 0 {\displaystyle g(n)>0} n {\displaystyle n}
コンピュータサイエンスと組合せ論では、大 、大シータ 、小 、小オメガ 、クヌースの大オメガ 表記法が使用される。 [3]
解析的数論では、大 、小 、ハーディの 、ハーディ–リトルウッドの大オメガ （+、-、±の添え字の有無にかかわらず）、ヴィノグラドフの 、 表記法がよく使用される 。 [9] [4] [10]
小オメガ 表記法は解析学や数論ではあまり使用されない。 [17] O {\displaystyle O} Θ {\displaystyle \Theta } o {\displaystyle o} ω {\displaystyle \omega } Ω {\displaystyle \Omega } O {\displaystyle O} o {\displaystyle o} ≍ {\displaystyle \asymp } Ω {\displaystyle \Omega } ≪ {\displaystyle \ll } ≫ {\displaystyle \gg } ∼ {\displaystyle \sim } ω {\displaystyle \omega }
異なる表記法を用いた近似値の品質 特にコンピュータサイエンスの分野では、大表記法は漸近的な 厳密な 境界を記述するために多少異なる意味で使用されることが多く、特定の状況 では大シータ 表記法を使用する方が事実上適切である可能性があります。 たとえば、関数 を考えるとき 、以下のすべては一般に受け入れられますが、より厳しい境界（以下の番号 2、3、4 など）は通常、より緩い境界（以下の番号 1 など）よりも強く好まれます。 O {\displaystyle O} Θ {\displaystyle \Theta } T ( n ) = 73 n 3 + 22 n 2 + 58 {\displaystyle T(n)=73n^{3}+22n^{2}+58}
T ( n ) = O ( n 100 ) {\displaystyle T(n)=O(n^{100})} T ( n ) = O ( n 3 ) {\displaystyle T(n)=O(n^{3})} T ( n ) = Θ ( n 3 ) {\displaystyle T(n)=\Theta (n^{3})} T ( n ) ∼ 73 n 3 {\displaystyle T(n)\sim 73n^{3}} として 。 n → ∞ {\displaystyle n\to \infty } これら3つの記述はすべて正しいですが、それぞれに含まれる情報は徐々に増えていきます。しかし、分野によっては、大きなO表記（上記のリストの2番目）の方が大きなTheta表記（上記のリストの3番目）よりも一般的に使用されることがあります。例えば、 入力サイズ に対する新しく開発されたアルゴリズムの実行時間を とすると 、アルゴリズムの発明者や利用者は、下限値や漸近的な挙動について明示的に述べずに、実行時間の上限値を設定する傾向があるかもしれません。 T ( n ) {\displaystyle T(n)} n {\displaystyle n}
バッハマン・ランダウ記法の拡張 コンピュータサイエンスで時々使用される別の表記法は （ ソフト O と読みます）であり、これは多対数因子を隠します。使用されている定義は 2 つあります。一部の著者は に対して を省略形として使用し [ 要出典 ] 、他の著者は を の省略形として使用します 。 が の多項式である 場合 、違いはありません。ただし、後者の定義では、例えば と言うことができますが、前者の定義では 任意の定数に対して が可能です 。一部の著者は、 後者の定義と同じ目的で O *と書きます。 [20] 本質的には、これはビッグ O 表記法であり、 対数因子を 無視します。これは、他の超対数関数の 増加率 効果が、悪い実行時パフォーマンスを予測する上で、対数増加因子によってもたらされる細かい点の影響よりも重要である大きな入力パラメータの増加率爆発を示しているためです。この表記法は、手元の問題に対してあまりに厳しい制限が課されていると述べられている成長率内での「細かい点を気にする」ことを避けるためによく使われます（ 任意の定数 と任意の O ~ {\displaystyle {\tilde {O}}} f ( n ) = O ~ ( g ( n ) ) {\displaystyle f(n)={\tilde {O}}(g(n))} f ( n ) = O ( g ( n ) log k n ) {\displaystyle f(n)=O(g(n)\log ^{k}n)} k {\displaystyle k} f ( n ) = O ( g ( n ) log k g ( n ) ) {\displaystyle f(n)=O(g(n)\log ^{k}g(n))} g ( n ) {\displaystyle g(n)} n {\displaystyle n} n 2 n = O ~ ( 2 n ) {\displaystyle n2^{n}={\tilde {O}}(2^{n})} log k n = O ~ ( 1 ) {\displaystyle \log ^{k}n={\tilde {O}}(1)} k {\displaystyle k} log k n = o ( n ε ) {\displaystyle \log ^{k}n=o(n^{\varepsilon })} k {\displaystyle k} ε > 0. {\displaystyle \varepsilon >0.}
また、 L 表記は 次のように定義される。
L n [ α , c ] = e ( c + o ( 1 ) ) ( ln n ) α ( ln ln n ) 1 − α , {\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }},} は、 に関して 多項式 と 指数関数 の間に位置する関数に便利です 。 log n {\displaystyle \log n}
任意のノルムベクトル空間 に値を取る関数への一般化は （絶対値をノルムに置き換えるだけで）単純である。ここで 、 と は 同じ空間に値を取る必要はない。 任意の位相群 に値を取る関数への一般化 も可能である [ 要出典 ] 。「極限過程」は、任意の フィルタ基数 を導入することで、すなわち有向 ネット と に 一般化することもできる 。この表記法は、ごく一般的な空間における 導関数 と 微分可能性 、そして関数の（漸近的）同値性 を定義するために使用できる。 f {\displaystyle f} g {\displaystyle g} g {\displaystyle g} x → x 0 {\displaystyle x\to x_{0}} f {\displaystyle f} g {\displaystyle g} o {\displaystyle o}
f ∼ g ⟺ ( f − g ) ∈ o ( g ) {\displaystyle f\sim g\iff (f-g)\in o(g)} これは 同値関係 であり、上記の 関係「 は」よりも制限的な概念です。 （ と が正の実数値関数である 場合、 に簡約されます 。）たとえば、 は ですが、 です 。 f {\displaystyle f} Θ ( g ) {\displaystyle \Theta (g)} lim f / g = 1 {\displaystyle \lim f/g=1} f {\displaystyle f} g {\displaystyle g} 2 x = Θ ( x ) {\displaystyle 2x=\Theta (x)} 2 x − x ≠ o ( x ) {\displaystyle 2x-x\neq o(x)}
歴史 ボワ・レイモンド、バッハマン・ランダウ、ハーディ、ヴィノグラドフ、クヌースの表記法の歴史を概説します。
1870年、ポール・デュ・ボワ＝レーモン [21] は、、、を それぞれ と 定義 した 。これらは広く採用されたわけではなく、今日では使われていない。最初の と 3番目の は対称性があり、 は と同じ意味である。後に、ランダウは より狭義の の極限が 1 に等しいという考え方 を採用した。 これらの表記法はいずれも今日では使われていない。 f ( x ) ≻ ϕ ( x ) {\displaystyle f(x)\succ \phi (x)} f ( x ) ∼ g ( x ) {\displaystyle f(x)\sim g(x)} f ( x ) ≺ ϕ ( x ) {\displaystyle f(x)\prec \phi (x)} lim x → ∞ f ( x ) ϕ ( x ) = ∞ , lim x → ∞ f ( x ) ϕ ( x ) > 0 , lim x → ∞ f ( x ) ϕ ( x ) = 0. {\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.} f ( x ) ≺ ϕ ( x ) {\displaystyle f(x)\prec \phi (x)} ϕ ( x ) ≻ f ( x ) {\displaystyle \phi (x)\succ f(x)} ∼ {\displaystyle \sim } f ( x ) / ϕ ( x ) {\displaystyle f(x)/\phi (x)}
記号Oは、数論者 ポール・バッハマン が1894年に著書 『 解析 数論 』第2巻で初めて導入しました。 [1] 数論者 エドムンド・ランダウが これを採用し、1909年にoという表記法を導入するきっかけとなりました。 [2] そのため、現在では両方ともランダウ記号と呼ばれています。これらの表記法は、1950年代の応用数学において漸近解析に用いられました。 [22] 記号（「 o ではない」という意味で ）は、1914年にハーディとリトルウッドによって導入されました。 [12] ハーディとリトルウッドは1916年に（「右」）と （「左」） という記号も導入しました。 [13] この表記法は、 少なくとも1950年代以降、数論においてある程度一般的に使用されるようになりました。 [23] Ω {\displaystyle \Omega } Ω R {\displaystyle \Omega _{R}} Ω L {\displaystyle \Omega _{L}} Ω {\displaystyle \Omega }
記号 は 、それ以前にも異なる意味で使用されていたが [21] 、 1909年にランダウ [2] によって、また1910年にハーディ [5] によって現代的な定義が与えられた。ハーディは、その論文の同じページで、記号 を定義した。 ここで は、 と が 両方 とも 満たされることを意味する。この表記法は現在でも解析的整数論で使用されている [24] [10] 。
ハーディは、論文の中で という記号も提案した。 ここで は、 ある定数に対してが満たさ れることを意味する （これはボア＝レーモンの表記法 に対応する ）。 ∼ {\displaystyle \sim } ≍ {\displaystyle \asymp } f ( x ) ≍ g ( x ) {\displaystyle f(x)\asymp g(x)} f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))} g ( x ) = O ( f ( x ) ) {\displaystyle g(x)=O(f(x))} ≍ − {\displaystyle \mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} } f ≍ − g {\displaystyle f\mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} g} f ∼ K g {\displaystyle f\sim Kg} K ≠ 0 {\displaystyle K\not =0} f ∼ g {\displaystyle f\sim g}
1930年代にヴィノグラドフ [6] は、
とという 表記法を普及させました。 これらはどちらも を意味します 。この表記法は解析的数論における標準となりました。 [4] f ( x ) ≪ g ( x ) {\displaystyle f(x)\ll g(x)} g ( x ) ≫ f ( x ) {\displaystyle g(x)\gg f(x)} f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))}
1970年代にビッグOは ドナルド・クヌース によってコンピュータサイエンスの分野で普及しました。クヌースはハーディのオメガ表記法に 別の表記法を提案し 、ハーディとリトルウッドのオメガ表記法に別の定義を提案しました。 [7] f ( x ) = Θ ( g ( x ) ) {\displaystyle f(x)=\Theta (g(x))} f ( x ) ≍ 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表記法 やのような表記法 とは異なり、暗黙の極限は存在しません。 のような表記法は、 表記法の乱用と みなされる可能性があります 。 x → ∞ {\displaystyle x\to \infty } Ω , Θ , ≫ , ≪ , ≍ {\displaystyle \Omega ,\Theta ,\gg ,\ll ,\asymp } ∼ {\displaystyle \sim } ω {\displaystyle \omega } f ( x ) = O ( g ( x ) ) ( x → ∞ ) {\displaystyle f(x)=O(g(x))\;\;(x\to \infty )}
等号 は、等号の使用が、この文には存在しない対称性を示唆し、誤解を招く可能性があるため、 表記法の乱用 であると 考える人もいます。de Bruijnが 言うように、 は真ですが、 はそうではありません。 [26] Knuthは 、このような文を「一方向性の等式」と表現しています。なぜなら、もし左右を逆にできると、「恒等 式とから 、のようなばかげたことを推論できるからです 。 」[27] Knuthは別の手紙で、次のことも指摘しています。 [28] f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))} O ( x ) = O ( x 2 ) {\displaystyle O(x)=O(x^{2})} O ( x 2 ) = O ( x ) {\displaystyle O(x^{2})=O(x)} n = n 2 {\displaystyle n=n^{2}} n = O ( n 2 ) {\displaystyle n=O(n^{2})} n 2 = O ( n 2 ) {\displaystyle n^{2}=O(n^{2})}
等号はこのような表記法に対して対称ではありません [この表記法では、] 数学者は英語の単語「is」と同じように「=」記号を慣習的に使用します。アリストテレスは人間ですが、人間は必ずしもアリストテレスであるとは限りません。
これらの理由から、集合記法 を用いて と 書き 、「 は の要素である 」または「 は集合に含まれる 」と読み、 を となる すべての関数のクラスと
考える人もいます 。 [27] しかし、等号の使用は慣例です。 [26] [27] より複雑な形式の式では、等号の方が便利です。 f ( x ) ∈ O ( g ( x ) ) {\displaystyle f(x)\in O(g(x))} f ( x ) {\displaystyle f(x)} O ( g ( x ) ) {\displaystyle O(g(x))} f ( x ) {\displaystyle f(x)} O ( g ( x ) ) {\displaystyle O(g(x))} O ( g ( x ) ) {\displaystyle O(g(x))} h ( x ) {\displaystyle h(x)} h ( x ) = O ( g ( x ) ) {\displaystyle h(x)=O(g(x))} f ( x ) = g ( x ) + O ( h ( x ) ) = O ( k ( x ) ) . {\displaystyle f(x)=g(x)+O(h(x))=O(k(x)).}
数論 [9] [4] [10] で広く用いられているヴィノグラドフ記法 とには、 この欠陥がない。なぜなら、これらの記法は、big-O記法が 等式 ではなく 不等式 を表すことをより明確に示しているからである。また、これらの記法は、big-O記法にはない対称性も備えている。つまり、
は と同じ意味である 。組合せ論やコンピュータサイエンスでは、これらの記法はほとんど見られない。 [3] ≪ {\displaystyle \ll } ≫ {\displaystyle \gg } f ( x ) ≪ g ( x ) {\displaystyle f(x)\ll g(x)} g ( x ) ≫ f ( x ) {\displaystyle g(x)\gg f(x)}
組版 ビッグオーは、以下の例のように、 イタリック体の大文字「 O 」 として表記されます。 [29] [30] TeX では 、数式モードで「O」と入力するだけで表示されます。ギリシャ語で「バッハマン・ランダウ」と呼ばれる表記法とは異なり、特別な記号は必要ありません。しかし、一部の著者はカリグラフィ表記法を使用しています 。 [31] [32] O ( n 2 ) {\displaystyle O(n^{2})} O {\displaystyle {\mathcal {O}}}
大文字の「O」は元々「order of」（"Ordnung"、Bachmann 1894）を表し、ラテン文字です。BachmannもLandauもこれを「Omicron」と呼ぶことはありません。この記号はずっと後（1976年）、Knuthによって大文字の「omicron」とみなされました[7]。これはおそらく、記号オメガの定義に由来すると思われます 。 数字 の ゼロ は 使用 す べきではありません。
参照
参考文献と注釈 ^ ab バックマン、ポール (1894)。 Analytische Zahlentheorie [ 解析的整数論 ] (ドイツ語)。 Vol. 2. ライプツィヒ：トイブナー。 ^ abcde ランドー、エドマンド (1909)。 Handbuch der Lehre von der Verreilung der Primzahlen [ 素数の分布理論に関するハンドブック ] (ドイツ語)。ライプツィヒ: BG トイブナー; 1974 年にチェルシー社から 2 冊 1 冊として再版され、ポール T. ベイトマン博士による付録が付けられました。 59～ 63ページ 。 ^ abcdef コーメン, トーマス・H. ; レイサーソン, チャールズ・E. ; リベスト, ロナルド・L. ; スタイン, クリフォード (2022). 「実行時間の特徴づけ」. アルゴリズム入門 （第4版）. MIT Press and McGraw-Hill. ISBN 978-0-262-53091-0 。 ^ abcdef イワニエツ、ヘンリク 、コワルスキー、エマニュエル. 解析的数論 、アメリカ数学会、2004年. ^ abcde Hardy, GH (1910). Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond. Cambridge University Press . p. 2. ^ abcd 例えば、「ウォーリング問題における G ( n ) の新たな推定値」（ロシア語）を参照。Doklady Akademii Nauk SSSR 5, No 5-6 (1934), 249–253。英語訳：Selected works / Ivan Matveevič Vinogradov; ソ連科学アカデミー・ステクロフ数学研究所が彼の90歳の誕生日を記念して作成。Springer-Verlag, 1985。 ^ abcdefghi ドナルド・クヌース（1976年4月～6月）「ビッグ・オミクロン、ビッグ・オメガ、ビッグ・シータ」 SIGACTニュース 8 ( 2): 18– 24. doi : 10.1145/1008328.1008329 . S2CID 5230246 . ^ シプサー、マイケル (2012). 計算理論入門 （第3版）. ボストン、マサチューセッツ州: PWS Publishing. ^ abcdef Ivić, A. (1985). リーマンゼータ関数 . John Wiley & Sons. 第9章. ^ abcdef Gérald Tenenbaum, Introduction to analytic and probabilistic number theory, « Notation », page xxiii. American Mathematical Society, Providence RI, 2015. ^ ザイデル、ライムンド （1991）、「台形分解の計算と多角形の三角形化のための単純かつ高速な増分ランダム化アルゴリズム」、 計算幾何学 、 1 ： 51-64 、 CiteSeerX 10.1.1.55.5877 、 doi ： 10.1016/0925-7721(91)90012-4 ^ abc Hardy, GH ; Littlewood, JE (1914). 「ディオファントス近似の問題：第2部 楕円θ関数に関連する三角級数」 Acta Mathematica . 37 : 225. doi : 10.1007/BF02401834 . 2018年12月12日時点のオリジナルよりアーカイブ。 2017年3月14日 閲覧 。 ^ ab Hardy, GH ; Littlewood, JE (1916). 「リーマンゼータ関数の理論と素数分布の理論への貢献」 Acta Mathematica 41 : 119–196 . doi : 10.1007/BF02422942. ^ E. ランダウ (1924)。 「Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV」[既知の領域の格子点の数について]。 ナクル。ゲゼル。ウィス。ゴット。数学物理学。 (ドイツ語): 137–150 。 ^ バルカサル、ホセ L.ガバロ、ホアキン。 「下限と上限によって指定される不均一な複雑さのクラス」 (PDF) 。 RAIRO – 理論情報学とアプリケーション – Informatique Théorique et Applications 。 23 (2): 180。ISSN 0988-3754 。 2017 年 3 月 14 日のオリジナルから アーカイブ (PDF) 。 2017 年 3 月 14 日 に取得 – Numdam 経由。 ^ 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 。 ^ 例えば、 Hildebrand, AJ「漸近的記法」 （PDF） では省略されています。数学部。 漸近的解析法 。Math 595、2009年秋。イリノイ州アーバナ：イリノイ大学。 2017年3月14日時点のオリジナルから アーカイブ （PDF） 。 2017年 3月14日 閲覧 。 ^ 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を参照してください。 ^ ab ボワ＝レイモンド、ポール・デュ (1870)。 「機能の無限の偉大なる相対性」。 アンナリ ディ マテマティカ、セリエ 2 。 4 : 338–353 。 土井 :10.1007/BF02420041。 ^ エルデイ, A. (1956). 漸近展開 . クーリエ社. ISBN 978-0-486-60318-6 。 。 ^ ECティッチマーシュ『リーマンゼータ関数の理論』（オックスフォード、クラレンドン出版社、1951年） ^ ハーディ, GH; ライト, EM (2008) [第1版 1938年]. 「1.6. いくつかの表記法」. 『数論入門』 . D.R. ヒース＝ブラウン と J.H. シルバーマンによる改訂版、 アンドリュー・ワイルズ による序文 （第6版）. オックスフォード: オックスフォード大学出版局. ISBN 978-0-19-921985-8 。 ^ ハーディ, GH (1966–1979). GHハーディ論文集（JEリトルウッドらとの共著を含む）全7巻 . クラレンドン・プレス, オックスフォード. ^ アブ ・デ・ブルーイン、NG (1958)。分析における漸近的手法。アムステルダム: 北オランダ。 5 ～ 7 ページ 。ISBN 978-0-486-64221-5 . 2023年1月17日時点のオリジナルよりアーカイブ 。 2021年9月15日 閲覧。 ^ abc グラハム, ロナルド ; クヌース, ドナルド ; パタシュニック, オレン (1994). コンクリート数学 (第2版). マサチューセッツ州レディング: アディソン・ウェスレー. p. 446. ISBN 978-0-201-55802-9 . 2023年1月17日時点のオリジナルよりアーカイブ 。 2016年9月23日 閲覧。 ^ 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 にアーカイブされています） ^ Donald E. Knuth, The art of computer programming. 第1巻. 基本アルゴリズム, 第3版, Addison Wesley Longman, 1997年. セクション1.2.11.1. ^ Ronald L. Graham、Donald E. Knuth、Oren Patashnik、 「Concrete Mathematics: A Foundation for Computer Science（第2版）」 、Addison-Wesley、1994年。セクション9.2、p.443。 ^ Sivaram Ambikasaran と Eric Darve、「 部分階層的半分離可能行列の高速直接ソルバー」、 J. Scientific Computing 57 (2013)、第3号、477–501ページ。 O ( N log N ) {\displaystyle {\mathcal {O}}(N\log N)} ^ Saket SaurabhとMeirav Zehavi、 「-Max-Cut: 時間アルゴリズムと多項式カーネル」、 Algorithmica 80 (2018)、第12号、3844–3860。 ( k , n − k ) {\displaystyle (k,n-k)} O ∗ ( 2 p ) {\displaystyle {\mathcal {O}}^{*}(2^{p})}
注記 ^ 入力の「サイズ」は通常、解くべき問題の難易度を示す指標として用いられます 。 答えを計算する（つまり問題を「解く」）ために必要な[実行]時間と[メモリ]容量は、問題のその インスタンスの難易度を示すものと考えられています。 計算複雑性理論 においては 、ビッグ 記法は、入力[データストリーム]のサイズ、必要な[実行]時間、必要な[メモリ]容量の3つすべてに対する[「桁数」の上限]として用いられます。 O {\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日 閲覧 .
外部リンク ウィキブックの データ構造には、 Big-O記法 に関するページがあります。
WikiversityはBig-O記法 を使ってMyOpenMathの問題を解きました
数列の成長 — OEIS（整数数列オンライン百科事典）Wiki 漸近記法入門 Big-O記法 – 何に役立つのか 一次導関数の中心差分法の精度におけるBig Oの例 アルゴリズムの複雑性分析へのやさしい入門 
![{\displaystyle [ca,c+a]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e02fd1ce170d298eb25a67b6199a7209892fee80)
![{\displaystyle {\begin{aligned}e^{x}&=1+x+{\frac {\;x^{2}\ }{2!}}+{\frac {\;x^{3}\ }{3!}}+{\frac {\;x^{4}\ }{4!}}+\dotsb &&{\text{ すべての有限 }}x について\\[4pt]&=1+x+{\frac {\;x^{2}\ }{2}}+O(|x|^{3})&&{\text{ すべての }}|x|\leq 1 について\\[4pt]&=1+x+O(x^{2})&&{\text{ すべての }}|x|\leq 1 について.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a4cf161e1f091b8a9c0dcaf25e35dc39d8770db)
![{\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40715162d91a34daf9bcfed5f41d8e336417f803)
![{\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/59b5d9f7b7c3e8763737cb136642c142bd27da00)
