オーダー - ushumpei’s blog

オーダーについて。適当に済ましていたので、おぼえがきします。アルゴリズムでも数学でも見ることがよくありますが、若干うろ覚えです。

定義

${ f(x) }$ が ${ x \rightarrow \infty }$ のときオーダー ${ O(g(x)) }$ である。

${ :\Longleftrightarrow }$

${}^\exists x_{0}, {}^\exists M > 0 \quad s.t. \quad {}^\forall x > x_{0} \Longrightarrow \vert f(x) \vert \lt M \vert g(x) \vert$

これを変形すると、 ${ \lim_{ x \rightarrow \infty } \left\vert \frac{ f(x) }{ g(x) } \right\vert \lt \infty }$ となることから、この定義は ${ f(x) }$ は ${ g(x) }$ より発散する速度が遅いということを意味しているのがわかります。この時 $f(x)$ は $g(x)$ で抑えられる、と言ったりするようです。

これに対し似た記法で、 $f(x) = o(g(x)) \quad x \rightarrow \infty$ というものもあります。この時、以下が成り立ちます。

${ \lim_{ x \rightarrow \infty } \left\vert \frac{ f(x) }{ g(x) } \right\vert = 0 }$

詳細な定義は省略しますが極限が0になることが違います。 $f(x)$ は $g(x)$ より発散する速度が、 $O(g(x))$ の時より、十分遅いというイメージです。この時 $f(x)$ は $g(x)$ に比べ無視できる、と言ったりするようです。例えば、写像 ${ f : { \mathbf R }^n \longrightarrow { \mathbf R }^m }$ が ${\bf x } = {\bf a }$ で全微分可能とは、

${ {}^\exists A : n \times m \, matrix \quad s.t. \quad f({\bf a} + {\bf h}) = f({\bf a}) + A {\bf h} + o(\vert\vert {\bf h} \vert\vert) }$

です。ここでは ${\bf h} \rightarrow 0$ となっていて多少変化がありますが基本的に意味は変わっていません。つまり、 $f({\bf a} + {\bf h})$ と $f({\bf a}) + A {\bf h}$ は ${\bf h}$ のノルムが十分小さいところでは限りなく等しいということが言えます。