ランダウの記号（ランダウのきごう、英: Landau symbol）は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
\(\delta \gt 0\)として、\( 0 \lt |t| \lt \delta\)の範囲で\( t \to 0\)のとき、\(t\)の関数の中で\(0\)に近づく関数の中で、同じ程度速く0に近づく関数をまとめるため、ランダウの記号を使う。
以下、
$$ g(t), h(t): 0 \lt |t| \lt \delta の範囲で定義されている$$
$$ t \neq 0 のとき h(t) \neq 0 $$
とする。
高次の無限小
$$ \lim_{t \to 0} \frac{g(t)}{h(t)} = 0$$
のとき、\(g(t)\)は\(h(t)\)よりも高次の無限小（高位の無限小）であるといい、
$$ g(t) = o (h(t)) \quad (t \to 0) $$
と表す。
\(o\)は英語の ‘order’ の小文字でスモールオー。
これは、\(g(t)\)のほうが\(h(t)\)より速く0に近づくことを意味する。
\(g(t) = t^2, h(t) = t\)で考えてみる。
\(t \to 0\)のとき、\(g(t) \to 0, h(t) \to 0\)である。
図を見ると、\(x=0\)付近では、直感的に\(g(t)\)のほうが\(h(t)\)より速く0に近づいているようである。
定義に基づき計算を行うと、
$$ \begin{align} \lim_{t \to 0} \frac{g(t)}{h(t)} &= \lim_{t \to 0} \frac{t^2}{t} \\ &= \lim_{t \to 0} t = 0 \end{align}$$
となり、
$$ g(t) = t^2 = o(t) $$
である。
つまり、\(t^2\)は\(t\)より高次の無限小である。（つまり、\(g(t)\)のほうが\(h(t)\)より速く0に近づく。）
ざっくり言うと、関数\(f(t) = h(t) + g(t) = t + t^2\)という関数を扱う時に、
$$ f(t) = h(t) + o(t) $$
なので、「近似的に\(g(t)\)は無視して\(f(t)=h(t)\)とします」、というような文脈で高次の無限小を使うことが多い。
ちなみに、商を逆にして計算してしてみると、
$$ \lim_{t \to 0} \frac{h(t)}{g(t)} = \lim_{t \to 0} \frac{1}{t} $$
となり、この場合は極限は存在しない。
同次の無限小
ある\(C\)が存在して、\(0 \lt |t| \lt \delta\)のすべての\(t\)に対して
$$ \frac{|g(t)|}{|h(t)|} \leq C $$
をみたすとき、\(g(t)\)と\(h(t)\)は同次の無限小（同位の無限小）であるといい、
$$ g(t) = O(h(t)) \quad (t \to 0) $$
と表す。
\(O\)は ‘order’ の大文字のオーでビッグオー。
これは、\(g(t)\)と\(h(t)\)は同じ程度速く0に近づくことを意味する。
\(g(t) = 2t, h(t) = t\)で考えてみる。
$$ \frac{|g(t)|}{|h(t)|} = \frac{2t}{t} = 2 $$
であり、
$$ g(t) = 2t = O(t) \quad (t \to 0) $$
となる。
これは、ざっくり言うと、
$$ g(t) = h(t) = O(t) $$
なので、「\(g(t)\)と\(h(t)\)は大体同じ関数として考えることができるね！」というような文脈で使う。
アルゴリズムの計算量でよく使われる。
ランダウの記号の性質
$$ m \leq n \implies o(t^m) + o(t^n) = o(t^m) \quad ( t \to 0) $$
を示す。
$$ f (t) = o(t^m), \ g(t) = o(t^n) $$
のとき、
$$ \lim_{t \to 0} \frac{f(t)}{t^m} = 0, \ \lim_{t \to 0} \frac{g(t)}{t^n} = 0 $$
ここで、
$$ \begin{align} \lim_{t \to 0} \frac{g(t)}{t^m} &=\lim_{t \to 0} \frac{g(t)}{t^n} t^{n-m} \\ &= \lim_{t \to 0} \frac{g(t)}{t^n}\lim_{t \to 0} t^{n-m} = 0 \end{align}$$
よって、
$$ \lim_{t \to 0} \left( \frac{f(t)}{t^m} + \frac{g(t)}{t^m} \right) = \lim_{t \to 0} \left( \frac{f(t)+g(t)}{t^m} \right) = 0 $$
$$ t^m o(t^n) = o(t^{m+n} ) \quad (t \to 0) $$
を示す。
$$ f(t) = o(t^n)$$
のとき、
$$ \lim_{t \to 0} \frac{f(t)}{t^n} = 0 $$
ここで、
$$ g(t) = t^m f(t)$$
とおくと、
$$ \lim_{t \to 0} \frac{g(t)}{t^{m+n}} = \lim_{t \to 0} \frac{t^m f(t)}{t^{m+n}} = \lim_{t \to 0} \frac{f(t)}{t^n} = 0 $$
$$ o(t^n) o(t^m) = o(t^{m+n}) $$
を示す。
$$ f(t) = o(t^n), \ g(t) = o(t^m) $$
のとき、
$$ \lim_{t \to 0} \frac{f(t)}{t^n} = 0, \ \lim_{t \to 0} \frac{g(t)}{t^m} = 0 $$
ここで、
$$ h(t) = f(t)g(t) $$
とおくと、
$$ \begin{align} \lim_{t \to 0} \frac{h(t)}{t^{n+m}} &= \lim_{t \to 0} \left( \frac{f(t)}{t^n} \right) \left( \frac{g(t)}{t^m} \right) \\ &= \left( \lim_{t \to 0} \frac{f(t)}{t^n} \right) \left( \lim_{t \to 0} \frac{g(t)}{t^m} \right) = 0 \end{align}$$