ときどき、途中に何かが入った奇妙な Θ 記号の Θ(n) を見たり、O(n) だけを見たりすることがあります。誰もこの記号を入力する方法を知らないので、単にタイプするのが面倒なのでしょうか、それとも別の意味でしょうか?
213410 次
9 に答える
632
簡単な説明:
アルゴリズムが Θ(g(n)) の場合、n (入力サイズ) が大きくなるにつれてアルゴリズムの実行時間が g(n) に比例することを意味します。
アルゴリズムが O(g(n)) の場合、n が大きくなったときのアルゴリズムの実行時間は、せいぜいg(n) に比例することを意味します。
通常、人々が O(g(n)) について話す場合でも、実際には Θ(g(n)) を意味しますが、技術的には違いがあります。
より技術的に：
O(n) は上限を表します。Θ(n) はタイト バウンドを意味します。Ω(n) は下限を表します。
f(x) = Θ(g(x)) f(x) = O(g(x)) および f(x) = Ω(g(x))
基本的に、アルゴリズムが O(n) であると言うとき、それは O(n 2 )、O(n 1000000 )、O(2 n ) でもありますが、Θ(n) アルゴリズムはΘ(n 2 )ではありません。 .
実際、f(n) = Θ(g(n)) は n の値が十分に大きいことを意味するため、f(n) は c の値によっては c 1 g(n) および c 2 g(n) の範囲内でバインドできます。 1および c 2、つまり、f の成長率は漸近的に g に等しくなります。g は f の下限および上限である可能性があります。これは、f が g の下限および上限にもなり得ることを直接意味します。その結果、
f(x) = Θ(g(x)) iff 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) = Θ(g(x)) iff f(x) = O(g(x)) および g(x) = O(f(x))
ω関数の緩い上限と緩い下限を表す、little-oh と little-omega ( ) 表記もあります。
要約する：
f(x) = O(g(x))(big-oh) は、 の成長率が の成長率f(x)以下であるg(x)ことを意味します。
f(x) = Ω(g(x))(big-omega) は、 の成長率f(x)が漸近的に の成長率以上であることを意味します。g(x)
f(x) = o(g(x))(little-oh) は、 の成長率が の成長率よりもf(x)漸近的に小さいことを意味します。g(x)
f(x) = ω(g(x))(リトルオメガ) は、 の成長率が の成長率よりもf(x)漸近的に大きいことを意味します。g(x)
f(x) = Θ(g(x))(theta) は、 の成長率が の成長率に漸近f(x)的に等しいことを意味します。g(x)
より詳細な議論については、ウィキペディアで定義を読むか、Cormen らによるアルゴリズム入門のような古典的な教科書を参照してください。
于 2009-01-22T23:00:00.597 に答える
56
1つは大きな「O」です
1つはビッグシータです
http://en.wikipedia.org/wiki/Big_O_notation
大きな O は、アルゴリズムが指定された式 (n^2) より多くのステップで実行されないことを意味します。
Big Omega は、指定された式 (n^2) よりも少ないステップでアルゴリズムが実行されることを意味します。
同じ式に対して両方の条件が真の場合、大きなシータ表記を使用できます....
于 2009-01-22T23:01:36.833 に答える
42
ここですでに美しく要約されている理論的な定義を提供するのではなく、簡単な例を挙げます。
の実行時間をf(i)としO(1)ます。以下は、漸近実行時間が であるコード フラグメントですΘ(n)。常にf(...) n関数timesを呼び出します。下限と上限の両方が n です。
for(int i=0; i<n; i++){
f(i);
}
以下の 2 番目のコード フラグメントには、漸近的な実行時間がO(n). f(...) ほとんど の場合、関数を呼び出しますn。上限は n ですが、 の内部で何が起こるかに応じて、下限はΩ(1)またはになる可能性があります。Ω(log(n))f2(i)
for(int i=0; i<n; i++){
if( f2(i) ) break;
f(i);
}
于 2012-09-27T19:17:55.620 に答える
11
グラフは、以前の回答を理解しやすくすることができます。
Θ-表記 - 同順 | O表記 - 上限
英語で、
左側には、上限と下限があり、どちらも同じ大きさ (つまりg(n) ) であることに注意してください。定数を無視し、上限と下限が同じ桁数である場合、f(n) = Θ(g(n))またはf(n) が g(n) の大きなシータにあると正当に言うことができます。
右側のより単純な例から始めて、上限g(n)は単に大きさのオーダーであり、定数cを無視すると言っています(すべてのビッグ O表記がそうであるように)。
于 2015-05-20T04:17:16.573 に答える
11
Theta は、大きな O と Omega が同じである特別な状況を表す簡単な方法です。
したがって、ある人が を主張する場合The Theta is expression q、彼らは必然的にBig O is expression qおよびも主張していOmega is expression qます。
大まかな類推:
If: Theta は、「その動物には 5 本の足があります」と主張します。Big O は真 (「その動物の足は 5 本以下」) であり、Omega は真 (「その動物の足は 5 本以上」) です。
式は必ずしも特定の数値ではなく、log(n)、n、n^2 などのさまざまな大きさの関数であるため、これは大まかな例えに過ぎません。
于 2015-01-07T06:58:18.080 に答える
6
f(n)O(n)if exists 正kとして属しますf(n)<=k*n
f(n)Θ(n)if existsに属し、正k1のk2ようにk1*n<=f(n)<=k2*n
于 2009-01-22T23:04:04.130 に答える
2
結論: 大きな O、大きな θ、大きな Ω は同じものと見なします。
なんで？以下にその理由を述べます。
最初に、1 つの間違ったステートメントを明確にします。一部の人々は、最悪の時間の複雑さだけを気にしていると考えているため、常に大きな θ の代わりに大きな O を使用します。この男はでたらめだと言います。上限と下限は 1 つの関数を説明するために使用され、時間の計算量を説明するためには使用されません。最悪の時間関数には上限と下限があります。ベストタイム関数にも上限と下限があります。
大きなOと大きなθの関係を分かりやすく説明するために、まず大きなOと小さなOの関係を説明します。定義から、小さな o が大きな O のサブセットであることは簡単にわかります。例：</p>
T(n)= n^2 + n、T(n)=O(n^2)、T(n)=O(n^3)、T(n)=O(n^4)と言えます。ただし、小さい o の場合、T(n)=o(n^2) は小さい o の定義を満たしていません。したがって、T(n)=o(n^3)、T(n)=o(n^4) は小さな o に対して正しいです。冗長な T(n)=O(n^2) とは何ですか? 大きいθです！
一般的に、大きなOはO(n^2)と言い、T(n)=O(n^3)、T(n)=O(n^4)とは言いません。なんで？無意識に大きなOを大きなθとみなしているからです。
同様に、無意識のうちに大きな Ω を大きな θ と見なします。
一言で言えば、大きなO、大きなθ、大きなΩは、定義上は同じものではありませんが、私たちの口と脳では同じものです。
于 2016-11-30T18:22:26.710 に答える