折りたたみを展開する

おぼえ書き、まとめ、発表など

ビッグオー記号について

 

ビッグオー記号とは

 

ビッグオー記号というものがある  f(n) = O(g(n)) とかそういうのだ。定義としては、ある  n_0 \in \mathbb{N} と定数  c が存在して、 n_0 \leq n \Longrightarrow f(n) \leq c g(n) であるというものだ。ランダウの記号とも呼ばれている。

 

f:id:Rlan:20170616095809p:plain

 

詳しくは、

 

mathtrain.jp

 

で解説されている。

 

落とし穴 

 

ここで注意しなくてはいけないのは、すべての n_0 についてcが見つかるとかそういうことではないことだ。つまり、発散の速さについてだけ興味があるので、一部で f(n) \geq g(n) となっててもいい。例えば、 f(n) = n, g(n) = n^2 0\leq n \leq 1  で   g(n) \leq f(n) だが、  f(n) = O(g(n)) である。

 

もしかして、当然の様に感じるかもしれない。定義通りではないかと。確かにそうである。ただ、注意しなくてはいけないのは、  g(n) \leq f(n) だからといって、  f(n) = O(g(n)) でないわけではないということである。ビッグオー記号記号を使ったこの式が示しているのは、関数  g の発散の速さが関数  f と同じかそれ以上ということだからだ。

 

次のような問題を考えてみればわかりやすい。

 

問題

 

いま、 f(n) = O(g(n)) である。 h(n) = 2^n と定義する。h(f(n)) = O(h(g(n)))は一般に成立するか?

 

答えは、否である。例えば、 f(n) = 2n g(n) = n とする。 f(n) = O(g(n)) である。たとえば、 c = 4 とすれば、  f(n) = 2n \leq 4n = c \times g(n) である。

 

 h(f(n)) = 4^n であり h(g(n)) = 2^n であるので、 f(n) = O(g(n)) ではない。 つまり、 h(f(n)) の発散を h(g(n)) の定数倍で抑えることはできない。もはや、 h(f(n)) の発散スピードは h(g(n)) 以上になってしまった。

 

ランダウの記号は大雑把に関数の発散を評価するので面白いが、思わぬ落とし穴があったようだ。