ランダウの記号 （ランダウのきごう、英 : Landau symbol ）は、主に関数の極限 における漸近的な挙動を比較するときに用いられる記法である。
スターリングの公式 はランダウの記号を用いて
ln
n
!
=
n
ln
n
−
n
+
O
(
ln
n
)
{\displaystyle \ln n!=n\ln n-n+O(\ln n)}
ランダウの漸近記法 (asymptotic notation) 、ランダウ記法 (Landau notation) あるいは主要な記号として O （数字の0ではない）を用いることから（バッハマン-ランダウの）O -記法 (Bachmann-Landau O-notation) 、ランダウのオミクロン などともいう。
記号 O はドイツ語 のOrdnung の頭字 にちなむ[2]
なおここでいうランダウはエトムント・ランダウ の事であり、『理論物理学教程 』の著者であるレフ・ランダウ とは別人である。
ランダウの記号は数学 や計算機科学 をはじめとした様々な分野で用いられる。
ランダウの記号
f
(
x
)
=
O
(
g
(
x
)
)
{\displaystyle f(x)=O(g(x))}
は 、x がじゅうぶん大きいとき関数 f が関数 g に比例もしくはそれ以下におさえられることを示す。
たとえば二次関数 3x 2 + 4x + 10 が x を限りなく大きくしたときどのように増大するかを考えると、変数 x が 2 より大きければ第一項 3x 2 が他の項より大きく、さらに大きくなるほど支配的になることがわかる。漸近解析をする上では定数 倍のような詳細は必要としないことが多く、O -記法を用いると、必要な情報を
3
x
2
+
4
x
+
10
=
O
(
x
2
)
{\displaystyle 3x^{2}+4x+10=O(x^{2})}
と端的に表すことができる。
このように関数 g としては関数 f よりも単純なもの（上の例では x 2 ）が通常用いられる。（#一般的なオーダー 参照。）
一方、ランダウの記号
f
(
x
)
=
o
(
g
(
x
)
)
{\displaystyle f(x)=o(g(x))}
は関数 f がおおよそ関数 g 未満であることを示している。
たとえば x が十分大きいとき 3x 2 + 4x + 10 は x 3 と比べると小さくなり、o -記法を用いると、これを
3
x
2
+
4
x
+
10
=
o
(
x
3
)
{\displaystyle 3x^{2}+4x+10=o(x^{3})}
と表すことができる。（ただし、o -記法よりも O -記法の方が多くの場合好ましいと考えられている。）
これまでは変数を限りなく大きくしたときを例に説明してきたが、他にも変数を限りなく小さくしたときや、定数に限りなく近づけたときの漸近挙動も同様にランダウ記法で表すことができる。どの意味で記号が用いられているのかを
f
(
x
)
=
O
(
g
(
x
)
)
(
x
→
∞
)
{\displaystyle f(x)=O(g(x))\quad (x\to \infty )}
のように明示する書き方もある。
f (x ) = O (g (x )), f (x ) = o (g (x )) (x → ∞) はそれぞれ
lim
x
→
∞
|
f
(
x
)
g
(
x
)
|
{\displaystyle \lim _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|}
lim
x
→
∞
|
f
(
x
)
g
(
x
)
|
=
0
{\displaystyle \lim _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|=0}
を表す。（厳密にはε-δ論法 で定義する。）特に f (x ) = o (1) は lim f (x ) = 0 と同値である。
ランダウ記法は様々な分野で有益であり、たとえば指数関数を3次までテイラー展開 したものは
e
x
=
1
+
x
+
x
2
2
!
+
x
3
3
!
+
O
(
x
4
)
(
x
→
0
)
{\displaystyle \mathrm {e} ^{x}=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+O(x^{4})\quad (x\to 0)}
と書き表せる。
記号 O とo は通常、関数の収束や発散の漸近的な上界を記述する為に用いられる。同様に漸近的な下界を記述する為にΩ, ωという類似記法が用いられ、上下両方を記述する為にΘ という記法を用いる。
ただし、Ω、ω、Θは主に計算機科学 で用いられる記法であり、数学 では O と o をこれらの意味に流用する事が多い（どの意味で用いているのかは文脈から判断）。
十分大きい全ての実数 x に対し定義されている実数値関数 f (x ) と g (x ) に対し、
f
(
x
)
=
O
(
g
(
x
)
)
(
x
→
∞
)
{\displaystyle f(x)=O(g(x))\quad (x\to \infty )}
を
∃
x
0
,
∃
M
>
0
s.t.
∀
x
[
x
>
x
0
⇒
|
f
(
x
)
|
≤
M
|
g
(
x
)
|
]
{\displaystyle {}^{\exists }x_{0},{}^{\exists }M>0\quad {\text{ s.t. }}\quad {}^{\forall }x\;[x>x_{0}\Rightarrow |f(x)|\leq M|g(x)|]}
と定義し、「f (x ) が x → ∞ のとき オーダーO (g (x )) である」と呼ぶ。
a を実数とするとき、a の近傍 で定義された実数値関数f (x ) と g (x ) に対し、
f
(
x
)
=
O
(
g
(
x
)
)
(
x
→
a
)
{\displaystyle f(x)=O(g(x))\quad (x\to a)}
を
∃
δ
>
0
,
∃
M
>
0
s.t.
∀
x
[
0
<
|
x
−
a
|
<
δ
⇒
|
f
(
x
)
|
≤
M
|
g
(
x
)
|
]
{\displaystyle {}^{\exists }\delta >0,{}^{\exists }M>0\quad {\text{ s.t. }}\quad {}^{\forall }x\;[0<|x-a|<\delta \Rightarrow |f(x)|\leq M|g(x)|]}
で定義し、「f (x ) が x → a のとき オーダーO (g (x )) である」と呼ぶ。
a の十分近くで g (x ) が 0 を値にとらない場合、
f
(
x
)
=
O
(
g
(
x
)
)
{\displaystyle f(x)=O(g(x))}
lim
¯
x
→
a
|
f
(
x
)
g
(
x
)
|
<
∞
{\displaystyle \varlimsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty }
が満たされることと同値である（a が∞の場合も同様）。特に f (x ) = O (1) は、近傍において f (x ) が有界 であることと同値である。
上で定義された
f
(
x
)
=
O
(
g
(
x
)
)
{\displaystyle f(x)=O(g(x))}
という記法は広く用いられている確立した慣習ではあるが紛らわしい記法の濫用 で、二つの関数が等しいという意味ではない。
この記法の濫用は、等号の両辺にO -記法が登場した際に問題となり、例えばx →∞のとき、
O
(
x
)
=
O
(
x
2
)
{\displaystyle O(x)=O(x^{2})}
O
(
x
2
)
≠
O
(
x
)
{\displaystyle O(x^{2})\neq O(x)}
すなわち、両辺にO -記法が登場した場合には、直観的には十分大きなx で左辺/右辺が定数未満になる事を意味する。
こうした記法上の問題を回避する為に、
f
∈
O
(
g
)
{\displaystyle f\in O(g)}
ないし、
f
(
x
)
≤
O
(
g
(
x
)
)
{\displaystyle f(x)\leq O(g(x))}
と書く流儀もあるが、一般的ではない。前者の場合、「O (g )」 は g の定数倍によって押さえられる関数全体からなる集合 であるとみなしていることになる。
より複雑な使い方としては、O ( ) が等式の異なる場所に複数、もちろん両辺にわたって複数回現れるというものがある。例えば、以下は 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}))(n+O(\log \,n))^{2}=n^{3}+O(n^{5/2}),\\&n^{O(1)}=O(e^{n}).\end{aligned}}}
これらの式の意味は、次のように解釈する：
左辺の O () を満たす「任意の」関数に対して、右辺の O () を満たす「ある」関数を適切に選べば、それらの関数を代入した等式の両辺が等しいようにできる。 例えば三つの目の式は、
任意の関数 f (n ) = O (1) に対し、g (n ) = O (e n g を適切に選べば
n
f
(
n
)
≤
g
(
n
)
{\displaystyle n^{f(n)}\leq g(n)}
事を意味する。
二つの目の式のように左辺に複数のO ()がある場合は、それらすべてに対して上述のルールを適用する。したがって二つの目の式は、
任意の関数
f
1
(
n
)
=
O
(
n
1
/
2
)
{\displaystyle f_{1}(n)=O(n^{1/2})\,}
f
2
(
n
)
=
O
(
O
(
log
n
)
)
{\displaystyle f_{2}(n)=O(O(\log \,n))\,}
g
(
n
)
=
O
(
n
5
/
2
)
{\displaystyle g(n)=O(n^{5/2})\,}
g を適切に選べば
(
n
+
f
1
(
n
)
)
(
n
+
f
2
(
n
)
)
2
≤
n
3
+
g
(
n
)
{\displaystyle (n+f_{1}(n))(n+f_{2}(n))^{2}\leq n^{3}+g(n)}
事を意味する。
漸近記法は多変数になっても有効である。たとえば
f
(
n
,
m
)
=
n
2
+
m
3
+
O
(
n
+
m
)
(
as
n
,
m
→
∞
)
{\displaystyle f(n,m)=n^{2}+m^{3}+O(n+m)\quad ({\mbox{as }}n,m\to \infty )}
という言及が示唆するのは、定数 C , N で
∀
n
,
m
>
N
:
|
g
(
n
,
m
)
|
≤
C
(
n
+
m
)
{\displaystyle \forall n,m>N:|g(n,m)|\leq C(n+m)}
を満たすものの存在である。ここで g (n , m ) は
f
(
n
,
m
)
=
n
2
+
m
3
+
g
(
n
,
m
)
{\displaystyle f(n,m)=n^{2}+m^{3}+g(n,m)}
で定められるものである。混乱を避けるためには、動かす変数は常に明示する必要がある。つまり
f
(
n
,
m
)
=
O
(
n
m
)
(
as
n
,
m
→
∞
)
{\displaystyle f(n,m)=O(n^{m})\quad ({\mbox{as }}n,m\to \infty )}
という言明は、次の
∀
m
:
f
(
n
,
m
)
=
O
(
n
m
)
(
as
n
→
∞
)
{\displaystyle \forall m:f(n,m)=O(n^{m})\quad ({\mbox{as }}n\to \infty )}
とは明確に異なる言明である。
O -記法と関連がある、Ω-記法、ω-記法、Θ-記法を導入する。
Ω-記法とω-記法はそれぞれ、O -記法とo -記法の定義で大小を反転させる事により得られる。Θ-記法Θ(g)は O(g) と Ω(g) を両方満たすことを意味する。
ただし、Ω-記法に関しては、この記法を初めて導入したハーディーとリトルウッド[2]
今日の定義との違いの要点をかいつまんでいえば、今日の定義ではΩ-記法は前述のようにO -記法の定義の大小反転だが、ハーディー達の定義ではΩ(g)はo(g) を満たさない事として定義していた。
両者の定義は性質のよい関数、例えば多項式に対しては同値だが、極限に近づく際に振動するような関数に関しては必ずしも同値ではない。
さらに見る 閉じる
また、計算機科学では
f
(
n
)
=
O
~
(
g
(
n
)
)
{\displaystyle f(n)={\tilde {O}}(g(n))}
を
∃
k
s.t.
f
(
n
)
=
O
(
g
(
n
)
log
k
(
g
(
n
)
)
)
{\displaystyle \exists k\quad {\text{ s.t. }}\quad f(n)=O(g(n)\log ^{k}(g(n)))}
の意味で用いる。対数因子を無視すればこれは本質的には O-記法である。この記法は "nit-picking" のクラスを記述するのにしばしば用いられる。これは logk n ) が任意の定数 k と正の定数 ε に対して常にo(n ε
関数のとりうる値は、絶対値をノルムに取り替えるだけでそのまま任意のノルム線型空間 の元に一般化できる。f や g は同じ空間に値を取る必要はない。g のとる値は任意の位相群 の元にすることも可能である。
「極限操作」"x → x 0 " は、勝手なフィルター基 の導入によって f と g の有向点族 として一般化される。
o -記法は微分 の定義や、極めて一般の空間における微分可能性を定義するのに有効である。また、関数の漸近同値を
f
∼
g
⟺
(
f
−
g
)
=
o
(
g
)
{\displaystyle f\sim g\iff (f-g)=o(g)}
と定めることができる。これは同値関係 であり、上述の f が Θ (g ) 程度であるという関係よりもなお強い制限を表す記法になっている。f と g が正値実数値関数なら lim f /g = 1 なる関係式に簡略化できる。例えば、2x は Θ (x ) のオーダーだが、 2x − x は o (x ) のオーダーでない。
計算機科学 、特に計算量理論 、アルゴリズム論 、暗号理論 では、アルゴリズムの計算時間を評価するのに O -記法を頻繁に用いる。
アルゴリズムの計算量の評価よく使われるO -記法関数の種類を示す。
これらの中でも特に重要なものには、個別の名称がついている(多項式時間 など)。
以下、 n はアルゴリズムに入力されるデータのビット 数を表す。
注意しなければならないのは、アルゴリズムに整数 N を入力するときである。N のビット数 n はおよそ log2 N なので、例えば「多項式時間」といったとき、これはN の多項式ではなく n の多項式を表す。
さらに見る
記法 名称 アルゴリズムの例
O
(
1
)
{\displaystyle O\left(1\right)}
定数時間 (Constant time)（整数の）偶奇判別
O
(
log
∗
n
)
{\displaystyle O\left(\log ^{*}n\right)}
反復対数 (iterated logarithmic)Hopcroft, Ullmanによる素集合データ構造 における探索アルゴリズム
O
(
log
n
)
{\displaystyle O\left(\log n\right)}
対数 (logarithmic)ソート済み配列における二分探索
O
(
n
c
)
,
0
<
∃
c
<
1
{\displaystyle O\left({n^{c}}\right),0<\exists c<1}
分数指数関数 (fractional power) kd木 上の探索
O
(
n
)
{\displaystyle O\left(n\right)}
線形関数 (linear)非ソート配列上の探索、離散ウェーブレット変換
O
(
n
log
n
)
{\displaystyle O\left(n\log n\right)}
準線形、線形対数 (linearithmic, loglinear, or quasilinear) ヒープソート 、高速フーリエ変換
O
(
n
2
)
{\displaystyle O\left({n^{2}}\right)}
二乗時間 (quadratic) 挿入ソート 、離散フーリエ変換
O
(
n
c
)
,
∃
c
≥
1
{\displaystyle O\left({n^{c}}\right),\exists c\geq 1}
多項式時間 (polynomial)ワーシャル-フロイド法
O
(
2
n
)
{\displaystyle O{(2^{n})}}
指数時間 (exponential , geometricとも) （現在最も速い）巡回セールスマン問題 の（厳密解の）解法
O
(
n
!
)
{\displaystyle O\left(n!\right)}
階乗 関数 (factorial, combinatorialとも)2つの論理式 の同型判定
O
(
2
c
n
)
∃
c
>
0
{\displaystyle O\left(2^{c^{n}}\right)\exists c>0}
二重指数時間 AC単一化子 の完備集合の探索
閉じる
一般的ではないが、更に発散速度の速い関数も存在する（アッカーマン関数 A(m, n ) など）。逆に更に発散速度の遅い関数として、逆関数 である逆アッカーマン関数 α(n ) などもあり、実際にあるアルゴリズムの計算量の見積りとして出現する。この関数は上界こそないものの、非常に発散速度が遅いために実用的には定数と見なされる (α(3) = 1, α(7) = 2, α(61) = 3,
α
(
2
2
2
65536
−
3
)
=
4
{\displaystyle \alpha (2^{2^{2^{65536}}}-3)=4}
O -記法はドイツの数論家であるポール・バッハマン によって1894年に彼の著書『解析数論』(Analytische Zahlentheorie [5] エドムント・ランダウ が1909年にo -記法を発明した。
なお、ハーディ とリトルウッド もランダウの記号
f
=
O
(
g
)
{\displaystyle f=O(g)\,}
f
⪯
g
{\displaystyle f\preceq g\,}
[2] [2]
またヴィノグラードフ （英語版 ）
f
=
O
(
g
)
{\displaystyle f=O(g)}
f
≪
g
{\displaystyle f\ll g}
[7]
ドナルド・クヌース は、計算機科学の世界にO -記法を導入し、Ω-記法やΘ-記法も再導入した。
関数 f (n ) が他の関数の有限和で表せるとき(多項式であるとき)、その内最も発散速度の速い関数が f (n ) のオーダーを決定づける。以下にその例を挙げる。
f
(
n
)
=
9
log
n
+
5
(
log
n
)
3
+
3
n
2
+
2
n
3
∈
O
(
n
3
)
.
{\displaystyle f(n)=9\log n+5(\log n)^{3}+3n^{2}+2n^{3}\in O(n^{3}).}
例での場合、係数を無視してn に関する項を見ると、log n 、(log n )3 n 2 n 3 n 3 n に関する項に関わらず、オーダーはO (n 3
特に、関数が n の多項式でおさえられるならば、n が無限大に発散するに従ってより低いオーダーの項まで無視できるようになる。
O (n c O (c n c がどれほど大きかろうと、後者の方がずっとずっと速く発散する。どのような定数 c に対しても n c 超多項式 (superpolynomial ) と呼ばれる。また、どのような定数 c に対しても c n 準指数関数 (subexponential ) と呼ばれる。アルゴリズムの計算量が超多項式かつ準指数関数であることもあり得る。例えば、現在知られている内で最も早い因数分解 のアルゴリズムもこれに含まれる。
O (log n ) と O (log(n c n c c log n より2つの指数関数は定数係数のみが異なり、これは big O -記法では無視されるからである。同様に異なる底を持つ対数関数も等価であるが、一方、異なる底を持つ指数関数は等価ではない。これはよくある勘違いである。例えば、2n n
入力サイズの単位の変更は、アルゴリズムの計算量を変えるかもしれないしそうでないかもしれない。単位を変更するということは、関数に現れる全ての n にある定数を掛けることと同じである。例えば、アルゴリズムが n 2 のオーダーで動くとき、n を cn で置き換えれば計算量は c 2 n 2 となり、big O -記法では c 2 は無視されるので計算量は変化しない (c 2 n 2 ∈ O (n 2 ))。しかし例えば 2n n を cn で置き換えると計算量は 2cn c n n c = 1 の場合を除く）。
次の多項式関数を考える
f
(
x
)
=
6
x
4
−
2
x
3
+
5
,
g
(
x
)
=
x
4
.
{\displaystyle {\begin{aligned}f(x)&=6x^{4}-2x^{3}+5,\\g(x)&=x^{4}.\end{aligned}}}
このとき、f (x ) のオーダーは O (g (x )) または O (x 4 ) である。実際、オーダーの定義からこれはある定数 C と x 0 が存在して、x 0 < x なる任意の x に対し | f (x )| ≤ C | g (x )| が成り立つことを意味するが、x > 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
≤
13
|
x
4
|
{\displaystyle {\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+2x^{3}+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&\leq 13x^{4}\\&\leq 13|x^{4}|\end{aligned}}}
であるから、C = 13, x 0 = 1 とおけばよい。
リーマン予想 が正しければ、x 以下の素数 の個数 π (x ) は次のように
π
(
x
)
=
∫
2
x
d
t
log
t
+
O
(
x
log
x
)
{\displaystyle \pi (x)=\int _{2}^{x}{\frac {dt}{\log t}}+O({\sqrt {x}}\,\log x)}
素数定理 も参照）。バブルソート の時間的計算量を考えると、n 個の要素からなる列をソートするのに掛かる時間はO (n 2 ) である。クイックソート を使えば、平均計算時間を O (n log n ) に改善できる（但し最悪時にはO (n 2 )）。n 次正方行列 の固有値 を求めるアルゴリズムは、少なくともその行列に含まれる n 2 個の要素を読み取らなければならない。従って、固有値を求めるアルゴリズムの時間的計算量の下界は Ω (n 2 ) である。すなわち、一般的な行列に対してその固有値を計算するのに掛かる時間が n 2 のオーダーを下回るアルゴリズムは存在しない。
O -記法はアルゴリズムの効率を解析するのに有用である。たとえば、あるサイズ n の問題(例えば処理すべきデータが n 個あるなど)を解くのに掛かる時間あるいは手順数が T (n ) = 4n 2 − 2n + 2 である場合を考える。
このとき、n を次第に大きくしていくと、 T (n ) に対して n 2 の項の影響が支配的になり、他の項はほとんど無視できるようになる（たとえば n = 500 としてみると、4n 2 の項は 2n の項の実に1000倍であり、後者を無視しても式に与える影響は、計算量を考える上でほとんど無視できる）。
さらに、n 3 や 2n T (n ) = 1,000,000n 2 のように係数が大きい関数と、それより指数が1大きい U (n ) = n 3 を比較する。仮に n = 1,000,000 としてみると T (1,000,000) = 1,000,000×1,000,0002 = 1,000,0003 = U (1,000,000) だから、n > 1,000,000 の場合は常に U (n ) > T (n ) である。）。
こうして残る影響をすくい上げて、O -記法では
T
(
n
)
∈
O
(
n
2
)
{\displaystyle T(n)\in O(n^{2})}
と書いて、「n 2 のオーダーである」と言い、これによってこのアルゴリズムの時間あるいは手順数T (n ) の増加具合が n 2 に支配されることを表現する。
日本数学会 編『岩波 数学辞典』（第4版）岩波書店 、2007年。ISBN 978-4-00-080309-0 。de Bruijn, N. G. (1981). Asymptotic Methods in Analysis Dover. ISBN 0-486-64221-6 . Zbl 0556.41021 . https://books.google.co.jp/books?id=7-wxAwAAQBAJ Graham, R. L.; Knuth, D. E.; Patashnik, O. (1994). Concrete Mathematics (Second ed.). Addison-Wesley. ISBN 0-201-55802-5 Marian Slodicka & Sandy Van Wontergem. Mathematical Analysis I . University of Ghent, 2004.
Donald Knuth (Apr.–June 1976). “Big Omicron and big Omega and big Theta” . ACM SIGACT News 8 (2): 18–24. doi :10.1145/1008328.1008329 . http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron.pdf .Donald Knuth. The Art of Computer Programming , Volume 1: Fundamental Algorithms , Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Section 1.2.11: Asymptotic Representations, pp.107– 123.
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . Introduction to Algorithms ISBN 0-262-03293-7 . Section 3.1: Asymptotic notation, pp.41–50.Michael Sipser (1997). Introduction to the Theory of Computation . PWS Publishing. ISBN 0-534-94728-X Jeremy Avigad, Kevin Donnelly. Formalizing O notation in Isabelle/HOL
Paul E. Black, "big-O notation" , in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 11 March 2005. Retrieved December 16, 2006.
Paul E. Black, "little-o notation" , in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.
Paul E. Black, "Ω" , in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.
Paul E. Black, "ω" , in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 29 November 2004. Retrieved December 16, 2006.
Paul E. Black, "Θ" , in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.
漸近展開 - テーラーの公式の一般化である関数の近似漸近最適 - 考えている問題の下界となる定数の範囲内に上界が漸近的に収まるようなアルゴリズムを記述する際にしばしば用いられる用語ハーディー記法 - 別の漸近記法ナックビンの定理 （英語版 ） 積分変換 の収束域について述べるためのもの 
, ...
, 
...
![{\displaystyle {}^{\exists }x_{0},{}^{\exists }M>0\quad {\text{ s.t. }}\quad {}^{\forall }x\;[x>x_{0}\Rightarrow |f(x)|\leq M|g(x)|]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/c991a21ee8cde1e9068da9fec7521cd4449582de)
![{\displaystyle {}^{\exists }\delta >0,{}^{\exists }M>0\quad {\text{ s.t. }}\quad {}^{\forall }x\;[0<|x-a|<\delta \Rightarrow |f(x)|\leq M|g(x)|]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/5844b952b46e4e6535096a5314cfcad51e8fedb0)
