202

私はビッグO、ビッグオメガ、ビッグシータ表記の違いについて本当に混乱しています。

ビッグOが上限で、ビッグオメガが下限であることは理解していますが、ビッグθ（シータ）は正確に何を表していますか？

タイトバウンドという意味だと読みましたが、どういう意味ですか？

4

6 に答える 6

365

まず、ビッグO、ビッグシータ、ビッグオメガとは何かを理解しましょう。それらはすべて関数のセットです。

ビッグOは上界と下界を与え、ビッグオメガは下界を与えています。ビッグシータは両方を提供します。

それはすべてですが、その逆でӨ(f(n))はありO(f(n))ません。 との両方にある場合は、に
T(n)あると言われます。セットの用語では、との共通部分ですӨ(f(n))O(f(n))Omega(f(n))
Ө(f(n))O(f(n))Omega(f(n))

たとえば、マージソートの最悪の場合はO(n*log(n))とOmega(n*log(n))-の両方であり、したがってもӨ(n*log(n))ですが、O(n^2)漸近n^2的にそれよりも「大きい」ため、もです。ただし、アルゴリズムがではないため、で はありません。Ө(n^2)Omega(n^2)

もう少し深い数学の説明

O(n)漸近的な上限です。の場合、T(n)あるから、のような定数が存在O(f(n))することを意味します。一方、big-Omegaは、次のような定数があると言います）。n0CT(n) <= C * f(n)C2T(n) >= C2 * f(n))

混同しないでください！

最悪、最良、および平均のケース分析と混同しないでください。3つすべて（オメガ、O、シータ）の表記は、アルゴリズムの最良、最悪、および平均のケース分析とは関係ありません。これらのそれぞれは、各分析に適用できます。

通常、アルゴリズムの複雑さを分析するために使用します（上記のマージソートの例のように）。「アルゴリズムAは」と言うとき、私たちが実際に意味するのは、「最悪の1ケース分析O(f(n))でのアルゴリズムの複雑さは」です。つまり、関数を「類似」（または正式には、それより悪くない）にスケーリングします。O(f(n))f(n)

なぜアルゴリズムの漸近限界を気にするのですか？

それには多くの理由がありますが、最も重要なのは次のとおりです。

  1. 正確な複雑さの関数を決定するのははるかに難しいため、理論的には十分な情報を提供するbig-O/big-Theta表記を「妥協」します。
  2. 正確な操作数もプラットフォームによって異なります。たとえば、16個の数値のベクトル（リスト）があるとします。どのくらいの操作が必要ですか？答えは：それは異なります。一部のCPUはベクトルの追加を許可しますが、他のCPUは許可しないため、実装やマシンによって答えが異なります。これは望ましくない特性です。ただし、big-O表記は、マシンと実装の間ではるかに一定です。

この問題を実証するために、次のグラフを見てください。 ここに画像の説明を入力してください

f(n) = 2*nよりも「悪い」ことは明らかですf(n) = n。しかし、他の機能との違いはそれほど劇的ではありません。f(n)=logn他の関数よりもはるかに低くなり、他の関数よりもはるかに高くなっていることがわかりf(n) = n^2ます。
したがって、上記の理由により、定数係数（グラフの例では2 *）を「無視」し、big-O表記のみを使用します。

上記の例でf(n)=n, f(n)=2*nは、はとの両方になりますO(n)-Omega(n)したがって、もになりTheta(n)ます。
一方、-f(n)=lognはO(n)（よりも「良い」f(n)=n）になりますが、Omega(n)-にはなりません。したがって、にもなりませんTheta(n)。
対称的には、f(n)=n^2になりますがOmega(n)、にはなりません。O(n)したがって、-もになりませんTheta(n)。

1通常、常にではありませんが。分析クラス（最悪、平均、最高）が欠落している場合、実際には最悪のケースを意味します。

于 2012-09-09T12:09:32.743 に答える
101

これは、アルゴリズムが特定の関数でbig-Oとbig-Omegaの両方であることを意味します。

たとえば、の場合、関数（実行時など）が十分に大きい場合よりも大きくなるようなӨ(n)定数があり、関数が十分に大きい場合よりも小さい定数があります。 kn*knKn*Kn

言い換えると、十分に大きいn場合、2つの線形関数の間に挟まれます。

十分に大きいk < Kため、nn*k < f(n) < n*K

于 2012-04-29T23:03:05.717 に答える
15

Theta（n）：との間に挟むことができる正の定数などが存在する場合、関数f(n)はに属します。つまり、上限と下限の両方を示します。Theta(g(n))c1c2f(n)c1(g(n))c2(g(n))

Theta（g（n））= {f（n）：0 <= c1（g（n））<= f（n）<= c2（g（n））となるような正の定数c1、c2、n1が存在しますすべてのn>=n1に対して}

私たちが言うとき、f(n)=c2(g(n))またはf(n)=c1(g(n))それは漸近的にタイトな境界を表します。

O（n）：上限のみを示します（タイトな場合とない場合があります）

O（g（n））= {f（n）：すべてのn>=n1に対して0<=f（n）<= cg（n）となるような正の定数cおよびn1が存在します}

例：境界2*(n^2) = O(n^2)は漸近的にタイトですが、境界は漸近的にタイトで2*n = O(n^2)はありません。

o（n）：上限のみを与えます（厳密な境界はありません）

O（n）とo（n）の顕著な違いは、f（n）がすべてのn> = n1でcg（n）未満であるが、O（n）のように等しくないことです。

例：2*n = o(n^2)、しかし2*(n^2) != o(n^2)

于 2012-09-12T00:46:21.707 に答える
6

これが古典的なCLRS（66ページ） で見つけたいものであることを願っています。ここに画像の説明を入力してください

于 2019-04-02T10:24:01.290 に答える
2

ビッグシータ表記：

バディを台無しにするものは何もありません！

正の値の関数f（n）があり、g（n）が正の値の引数nを取る場合、{f（n）として定義されるϴ（g（n））：すべてのn>に対して定数c1、c2、およびn1が存在します。 = n1}

ここで、c1 g（n）<= f（n）<= c2 g（n）

例を見てみましょう：

f（n）=

g（n）=

c1=5およびc2=8およびn1=1

すべての表記法の中で、ϴ表記法は、それぞれ上限と下限を与えるbig-ohとbig-omegaとは異なり、タイトな境界を与えるため、関数の成長率について最も直感的に理解できます。

ϴは、g（n）がf（n）にできるだけ近く、g（n）の成長率がf（n）の成長率に可能な限り近いことを示しています。

より良い直感を得るために画像を参照してください

于 2018-10-16T16:15:15.687 に答える
1

まず第一に理論

  1. ビッグO=上限O（n）

  2. シータ=注文関数-theta（n）

  3. オメガ=Q-表記（下限）Q（n）

なぜ人々はそんなに混乱しているのですか？

多くのブログや本では、このステートメントがどのように強調されているかは次のとおりです。

「これはBigO（n ^ 3）です」など。

そして人々はしばしば天気のように混乱します

O（n）== theta（n）== Q（n）

しかし、覚えておく価値があるのは、それらがO、Theta、Omegaという名前の単なる数学関数であるということです。

したがって、それらは同じ多項式の一般式を持ち、

させて、

f（n）= 2n4 + 100n2 + 10n + 50すると、

g（n）= n4なので、g（n）は関数を入力として受け取り、最大のパワーで変数を返す関数です。

以下のすべての説明について同じf（n）＆g（n）

Big O（n）-上界を提供します

Big O（n4）= 3n4、3n4>2n4であるため

3n4はBigO（n4）の値です。f（x）=3xと同じです。

n4はここでxの役割を果たしているので、

n4をx'so、Big O（x'）= 2x'に置き換えます。これで、私たちは両方とも満足しています。

したがって、0≤f（n）≤O （x'）

O（x'）= cg（n）= 3n4

価値を置く、

0≤2n4+100n2+10n+50≤3n4

3n4は私たちの上限です

Big Omega（n）-下限を提供します

Theta（n4）= cg（n）= 2n42n4≤この例のf（n）であるため

2n4はシータ（n4）の値です

したがって、0≤cg（n）≤f（n）

0≤2n4≤2n4+100n2+ 10n + 50

2n4は私たちの下限です

Theta（n）-タイトバウンドを提供します

これは、天気の下限が上限に類似していることを確認するために計算されます。

ケース1）。上界は下界に似ています

if Upper Bound is Similar to Lower Bound, The Average Case is Similar

Example, 2n4 ≤ f(x) ≤ 2n4,
Then Theta(n) = 2n4

ケース2）。上界が下界と類似していない場合

In this case, Theta(n) is not fixed but Theta(n) is the set of functions with the same order of growth as g(n).

Example 2n4 ≤ f(x) ≤ 3n4, This is Our Default Case,
Then, Theta(n) = c'n4, is a set of functions with 2 ≤ c' ≤ 3

これが説明されることを願っています!!

于 2019-11-14T11:55:42.717 に答える