はなちるのマイノート

Unityをメインとした技術ブログ。自分らしくまったりやっていきたいと思いますー！

トップ > アルゴリズム > アルゴリズムイントロダクション第3章の個人まとめ

アルゴリズムイントロダクション第3章の個人まとめ

アルゴリズム 勉強メモ

はじめに

前回の続きをやっていきたいと思います。
www.hanachiru-blog.com

ちなみに内容的には昔書いたこの記事とかなり似ている感じでした。
www.hanachiru-blog.com


第3章「関数の増加」

Θ記法

ある与えられた関数 g(n)に対して、 \Theta(g(n))を関数の集合と定義する。

\Theta(g(n)) = \{f(n): ある正の定数c_1,c_2,n_0が存在して、 すべてのn\geq n_0に対して0\leq c_1g(n) \leq f(n) \leq c_2g(n)　を満たす \}

O記法

Θ記法は関数を漸近的に上下から限定するのに対して、漸近的上界だけ関心があるときはO記法を用いる。

O(g(n)) = \{ f(n):ある正の定数c,n_0が存在して、すべてのn\geq n_0に対して0 \leq f(n) \leq cg(n)を満たす \}

Ω記法

Θ記法は関数を漸近的に上下から限定するのに対して、漸近的下界だけ関心があるときはΩ記法を用いる。

Ω(g(n)) = \{ f(n):ある正の定数c,n_0が存在して、すべてのn\geq n_0に対して0 \leq cg(n) \leq f(n)を満たす \}

o記法

こちらはアルゴリズムを考える上ではあまり使われないやや発展的内容。

O記法(ビッグオー)が与える漸近的上界は常に漸近的にタイトであるとは限らない。つまり 2n = O(n^2)が成立する。

対して o記法（リトルオー）は漸近的にタイトでない上界を表すのに用いられる。

o(g(n)) = \{ f(n) : 任意の正の定数c>0に対して、ある正の定数n_0が存在して、
すべてのn\geq n_0 に対して 0 \leq f(n) \leq cg(n)を満たす \}

2n = o(n^2)であるが、 2n^2 \neq o(n^2)となる。

イメージとしてはO記法は \leqで、o記法は <な感じ。

ω記法

同様にやや発展的。

o記法と同じ感じで、漸近的にタイトでない下界を表すのにω記法を用いる。

\omega (g(n)) = \{ f(n) : 任意の正の定数c>0に対して、ある正の定数n_0が存在して、
すべてのn\geq n_0 に対して 0 \leq cg(n) \leq f(n)を満たす \}

さいごに

www.hanachiru-blog.com