Ｏ記法の値について

質問

アルゴリズムの計算量を示すのにＯ記法というのがありますが、Ｏ記法って定数係数や次数の低い係数を無視しますよね。
例えば、計算量が次の式になる場合とか。

１．３ｎ＋２　→　Ｏ（ｎ）
２．５ｎ''＋３ｎ＋５　→　Ｏ（ｎ''）　（ｎ''はｎの２乗）
３．２ｎ'''－４ｎ＋３　→　Ｏ（ｎ'''）　（ｎ'''はｎの３乗）

どうして、定数係数や次数の低い係数を無視するのでしょうか？

回答No.2

Yune-Kichi · ベストアンサー

> ＞nがあるNより大きいときに，
> このＮというのは何を示しているのでしょうか？
> ここではＮ＝２としてましたが、このＮは任意の値でしょうか？それとも定数項の２でしょうか？

定数ではないですし，任意のNに対する話でもないです。
nが正の方向へ大きくなっていくとき，N以下では|kg(n)|<=|f(n)|かもしれないが，Nをこえれば常に|f(n)|<|kg(n)|となるkとNが存在するという主張の為のNです。

> あと、この定義が成り立つようにｇ（ｎ）を定めようとすると、条件に合致するｇ（ｎ）が沢山出てきそうな気がするのですが、ｇ（ｎ）が沢山存在したら不都合とかは無いのでしょうか？
たくさん存在するような定義です。

実際にはf(n)∈Ο(g(n))となるg(n)の中で，一番発散速度の遅い物が使われることが多いと思います。
このため，Ο(g(n))をΘ(g(n))のように使っていることも多いと思いますよ。

Ο(g(n))：上界。n > Nで常に|f(n)| < |kg(n)|。5n^2 + 3n + 5ならΟ(n^2), Ο(n^2 log n), Ο(n^3)等。
Ω(g(n))：下界。n > Nで常に|f(n)| > |kg(n)|。5n^2 + 3n + 5ならΩ(n^2), Ω(n log n), Ω(n)等。
Θ(g(n))：上界かつ下界。言い換えると，f(n)∈Ο(g(n))かつf(n)∈Ω(g(n))。5n^2 + 3n + 5ならΘ(n^2)。

お礼

Ｏ記法って沢山存在するように定義されたものだったのですか。
Ｏ記法って複雑ですね。条件に合致する値を見つけるのが大変そう・・・

回答ありがとうございました。

補足

ずいぶん定義が複雑なのですが、このような定義でどうしてアルゴリズムの計算量が求められるのでしょうか？

回答No.1

Yune-Kichi

無視しているのではなく，定義から単純にそう見えるだけです。

f(n)∈Ο(g(n))とは，
nがあるNより大きいときに，うまいこと定数kをとると，
|f(n)|<|kg(n)|が常に成り立つ，という主張です。

1の例で言えば，f(n)=3n+2，g(n)=nです。
この時，n>2の時に常に|f(n)| < |4g(n)|が成立しますから，
3n+2∈Ο(n)と言えます。
実際には，g(n)=n^2としても (n^mはnのm乗)，
n>2の時に常に|f(n)| < |2g(n)|が成立しますから，
3n+2∈Ο(n^2)とも言えます。

お礼

Ｏ記法の定義ってこんなにややこしかったのですか。
単純に、定数係数と次数の低い係数を省いただけなのかと思ってました。

回答ありがとうございました。

補足

＞nがあるNより大きいときに，

このＮというのは何を示しているのでしょうか？
ここではＮ＝２としてましたが、このＮは任意の値でしょうか？それとも定数項の２でしょうか？

あと、この定義が成り立つようにｇ（ｎ）を定めようとすると、条件に合致するｇ（ｎ）が沢山出てきそうな気がするのですが、ｇ（ｎ）が沢山存在したら不都合とかは無いのでしょうか？