計算量の上界を見るときにビッグオー記法などとよく引き合いに出される、例のランダウの記号というやつについて、解析学のテキストで触れられているものを読んだ。「他の定理はともかくとしてこれなら知っているぞ」といわんばかりの思いで臨んだが、数学的定義のちんぷんかんぷんさに打ちのめされた。とはいえひとまずテキストの内容は理解できたと信じて、この定義を忘れないようにしたいとメモを書いておく。
収束速度の表現
[tex: x \to a] のとき [tex: 0] に収束するふたつの関数を考える。 [tex: a = 0] として [tex: x \to 0] と考えてもよい。
[tex: \displaystyle \lim_{x \to a}{\varphi(x)} = 0 ]
[tex: \displaystyle \lim_{x \to a}{\psi(x)} = 0 ]
[tex: \sim] 記号
[tex: \displaystyle \varphi(x) \sim \psi(x) ] と書いて [tex: \displaystyle \lim_{x \to a}{\frac{\varphi(x)}{\psi(x)}} = 1 ] を意味する。
[tex: \displaystyle \varphi(x)] と [tex: \displaystyle \psi(x)] が同じ速さで [tex: 0] に収束するということ。
[tex: o] （スモールオー）記号
[tex: \displaystyle \varphi(x) = o(\psi(x)) ] と書いて [tex: \displaystyle \lim_{x \to a}{\frac{\varphi(x)}{\psi(x)}} = 0 ] を意味する。
[tex: \displaystyle \varphi(x)] が [tex: \displaystyle \psi(x)] よりも速く [tex: 0] にいくということで、このとき [tex: \varphi(x)] は [tex: \psi(x)] より 高位の無限小 という。
[tex: O] （ビッグオー）記号
正の数 [tex: K] があって
| [tex: \displaystyle | \frac{\varphi(x)}{\psi(x)} | \leq K, x \to a] |
のとき [tex: \varphi(x) = O(\psi(x))] と書く。
「 [tex: O(\psi(x))] は [tex: \psi(x)] で割って [tex: K] で上から抑えられる数」と覚えればよい。
発散速度の表現
[tex: x \to \infty] のときもだいたい同じ感じで表現できる。ここでは省略。
テイラー展開の表現
[tex: Rn] を剰余項としてこんな風に書くことにする。
[tex: \displaystyle f(x) = f(a) + f’(a)(x-a) + \frac{f’‘(a)}{2!}(x-a)^{2} + \cdots \\ \displaystyle + \frac{f^{(n-1)(a)}}{(n-1)!}(x-a)^{n-1} + Rn, x \to a ]
このときに [tex: Rn] が [tex: (x - a)^{n}] で割れてかつ正数 [tex: K] で上から抑えられるので、
[tex: \displaystyle Rn = O( (x - a)^{n} ) ]
とも表現できるわけである。
さらに [tex: (x-a)^{n}] は [tex: (x-a)^{n-1}] より高位の無限小なので
[tex: \displaystyle Rn = o((x-a)^{n-1}) ]
としてしまってもよい。
不定形の極限を計算するときには、テイラー展開を上手に使って [tex: O( (x-a)^{n} )] を [tex: o(1)] のような形に持ち込みたい。 [tex: o(1)] はつまり「[tex: 1] で割って [tex: 0] になる数」として処理できる（無視できる）ことになり、 [tex: \displaystyle \lim_{x \to 0}{(x + o( 1 ) )} = 0] のように計算できる。
たとえばこのように:
[tex: \displaystyle \lim_{x \to 0}{\frac{\log(1+x) - x}{x^{2}}} \\displaystyle = \lim_{x \to 0} {\frac{( x - \frac{1}{2} x^{2} + O(x^{3}) ) - x}{x^{2}}} \\displaystyle = \lim_{x \to 0} {\frac{- \frac{1}{2} x^{2} + o(x^{2})}{x^{2}}} \\displaystyle = \lim_{x \to 0} {( - \frac{1}{2} + o( 1 ) )} \\displaystyle = - \frac{1}{2} ]