読者です 読者をやめる 読者になる 読者になる

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} のノルムが十分小さいところでは限りなく等しいということが言えます。

アルゴリズムなどではよく、 O(n) O(\sqrt{n}) などと言ったりしますね。これらは「入力データ量  n に対する実行時間は  O(n)」みたいな文脈だったと思います。これはつまり、

  \lim_{ n \rightarrow \infty } \left\vert \frac{ \text{ アルゴリズムの実行時間 } }{  (n: \text{入力データ量} ) } \right\vert = const \lt \infty

より、

 \text{ アルゴリズムの実行時間 } =  const \times (n: \text{入力データ量})

この場合はアルゴリズムの実行時間が  n に比例する、ということですね。 n^2 なども同様です。

感想

わかったようなわかってないような微妙な気分です。当たり前のことを言っている気持ちにもなりました。

まあ少なくとも毎回ググらなくてよくなっただけ、進歩かと思います。