[解決済み】Θ(n)とO(n)の違いは何ですか？）

質問

Θ(n)の真ん中に何かある変なΘの記号があるときと、ただのO(n)のときがあります。この記号の打ち方を誰も知らないので、ただ単に打ち方が悪いのか、それとも何か違う意味があるのでしょうか？

どのように解決するのですか？

簡単に説明します。

あるアルゴリズムがΘ(g(n))の場合、n（入力サイズ）が大きくなるにつれて、そのアルゴリズムの実行時間がg(n)に比例することを意味します。

あるアルゴリズムが O(g(n)) であれば、n が大きくなったときの実行時間が せいぜい g(n)に比例する。

通常、O(g(n))と言われても、実際にはΘ(g(n))のことですが、厳密には違いがあるんですね。

もっと技術的に

O(n)は上界を表します。Θ(n)は、タイトバウンドを意味する。 Ω(n)は下限を表す。

<ブロッククオート

f(x) = Θ(g(x)) if f(x) = (x)の場合。 O(g(x))かつf(x)=Ω(g(x))

基本的にあるアルゴリズムがO(n)であると言うとき、それはまたO(n)である。 ² )、O(n ^1000000 ), O(2 ⁿ ), ... しかし、Θ(n)アルゴリズムは ではなく Θ(n ² ).

実際、f(n) = Θ(g(n)) なので、nが十分に大きい値であれば、f(n)はc以内での束縛が可能であることを意味する。 <サブ 1 g(n)とc <サブ 2 g(n) のある値に対する c <サブ 1 とc <サブ 2 すなわち，fの成長率は漸近的にgに等しく，gは下界となりうる。 と このことは、fがgの下界と上界になりうることを直接的に意味している。その結果

f(x) = Θ(g(x)) if g(x) = Θ(f(x))

同様に、f(n) = Θ(g(n)) を示すには、gがfの上界（つまりf(n) = O(g(n))）で、fがgの下界（つまりf(n) = Ω(g(n)) g(n) = O(f(n)) と全く同じこと）であれば良いのです。簡潔に言えば

f(x) = O(g(x)) かつ g(x) = O(f(x)) ならば、f(x) = Θ(g(x))

リトル・オーやリトル・オメガもありますよ( ω ) 関数の緩い上界と緩い下界を表す記法です。

要約すると

f(x) = O(g(x)) (ビッグ・オー)とは の成長率は f(x) は 漸近的に 以下 になります。 の成長率に g(x) .

f(x) = Ω(g(x)) (big-omega）とは の成長率が低下していること。 f(x) は 漸近的に よりも大きいか に等しい。 の成長率は g(x)

f(x) = o(g(x)) (リトル・オー)とは の成長率は f(x) は 漸近的に 未満 その の成長率 g(x) .

f(x) = ω(g(x)) (リトルオメガ）とは の成長率が低下していること。 f(x) は 漸近的に よりも大きい その の成長率 g(x)

f(x) = Θ(g(x)) (シータ)は、以下のことを意味します。 の成長率は f(x) は 漸近的に に等しい。 その の成長率 g(x)

より詳しい解説は ウィキペディアの定義を読む あるいは、CormenらのIntroduction to Algorithmsのような古典的な教科書を参照してください。