の違いは何ですかΘ(n)とO(n)?
https://stackoverflow.com/questions/471199
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
もっΘ(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))iff f(x)= O(g(x))とf(x)=Ω(g(x))
基本的にといってもアルゴリズムはO(n)でもO(n2)O(n1000000)、(2n),...がΘ(n)アルゴリズム ない Θ(n2).
実際、f(n)=Θ(g(n))とは十分に大きな価値をn、f(n)で拘束されること以内c1g(n)c2g(n)一部の値がc1 c2, （の成長率は漸近的に等しいg:gき下 や とされる。このことを直接は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))
もあり少しあとちょっとオメガ(ω 記述を表す上でゆったりとゆったりするとは限の機能です。
をまとめ:
f(x) = O(g(x))（-oh）のとき の成長率のf(x)は 漸近的 以下の へ の成長率のg(x).
f(x) = Ω(g(x))(大のオメガ） の成長率f(x)は 漸近的 以上 等しい の成長率のg(x)
f(x) = o(g(x))（-oh）のとき の成長率のf(x)は 漸近的 以上 の 成長率のg(x).
f(x) = ω(g(x))(っ-ω） の成長率f(x)は 漸近的 以上 の 成長率のg(x)
f(x) = Θ(g(x))(theta)こ の成長率のf(x)は 漸近的 等しい の 成長率のg(x)
より詳細な議論ができ の定義をWikipediaで調べる または相談するクラシックの教科書などを紹介アルゴリズムによるCormen et al.
他のヒント
何を意味している表記法を覚えてする簡単な方法（トリックは、私が推測する）あります。
ビッグ-O表記のすべてのバーを有すると考えることができます。
Ωを見ると、それが結合した低級（漸近）であるように、、バーは、下にある。
Θを見ているときに、バーが真ん中に明らかです。だから、タイトバインド（漸近）です。
Oを手書きすると、あなたは通常、上部に仕上げ、および波線を描きます。したがって、O（n）は関数の上限です。公平を期すために、これはほとんどのフォントでは動作しませんが、それは名前の元の正当化である。
1が大きい "O"
1ビッグシータである
http://en.wikipedia.org/wiki/Big_O_notationする
ビッグOは、あなたのアルゴリズムは、与えられた式に比べてこれ以上の手順で実行することを意味し（N ^ 2）
ビッグオメガは、
あなたのアルゴリズムは、与えられた式（N ^ 2）におけるよりも少ないステップで実行することを意味します両方の条件が同じ発現に該当する場合は、あなたは大きなシータ記法を使用することができます....
美しく、すでにここに要約されている理論的な定義を提供するのではなく、私は簡単な例をあげるます：
f(i) O(1)の実行時間があるとします。以下はその漸近ランタイムΘ(n)あるコードの断片です。それの常にの機能f(...) n回を呼び出します。下限と上限の両方Nである。
for(int i=0; i<n; i++){
f(i);
}
第2のコードフラグメントは、以下O(n)の漸近的な実行時間を有します。これは、ほとんどののΩ(1)の回での Ω(log(n))関数を呼び出します。上限は、Nであるが、下限はf2(i)内部に何が起こるかに応じて、<=>又は<=>とすることができます。
for(int i=0; i<n; i++){
if( f2(i) ) break;
f(i);
}
シータはどこ特別situtationに言及する簡便な方法であります ビッグOとオメガは同じです。
このように、一方が主張する場合The Theta is expression q、それらはまた、必ずしも主張されるBig O is expression qとOmega is expression q。
ラフ類推ます：
の場合： シータ「は、動物が5脚を持っていること。」、と主張します それはそれは、次のとおりです。 ビッグOが真である（「その動物は、5足以下の持っています。」） そして オメガが真である（「その動物が5脚よりも多い又は等しいされています。」）
これは2 ^表現は必ずしも特定の数、そのようなログ（n）と桁を変えるのではなく、機能があるためだけ粗い同様だ、N、N、（など）。
A チャートには、以前の答えは簡単に作ることができます理解する：
Θ-表記 - 同じ順序| O-表記 - 上限
英語で、
左側に、同じ大きさのオーダーの両方とも、その上限と下限があることに注意し（すなわち、 G（N））。定数を無視し、そしてもし上限と下限の大きさの同じ順序を有する、一方が有効に言うことができ、 F（N）=Θ（G（N））又は F（N） G（N）の大きなシータにある
右、簡単な例から始めて、同じように（上限 G（N）のは、単に大きさのオーダーであり、 C の定数を無視して言っていますすべてののビッグO の表記ん）。
結論：私たちは同じものとして大きなO、大きなθと大きなΩを考えています。
なぜ？私は以下の理由を教えてくれます。
まず、私は1つの間違った文を明確にし、一部の人々は、我々だけで最悪の時間の複雑さを気にしていることだと思うので、私たちはいつもの代わりに大きなθの大きなOを使用します。私はこの男がbullshittingされると言うだろう。上下の境界は、一つの機能を記述するために使用される時間の複雑さを記述するために使用されていません。最悪の時間関数は、その上限と下限があります。ベストタイム機能は、その上下あまりにも結合している。
はっきりと大きなOと大きなθとの関係を説明するために、私が最初にOビッグOと小さなとの関係を説明します。定義から、我々は簡単に小さなoは例えば大きなO.のサブセットであることを知ることができます：
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）は何ですか？これは大きなθだ！の
一般的に、我々はほとんどT（N）= O（N ^ 3）、T（N）= O（N ^ 4）を言うために、大きなOはO（N ^ 2）であると言います。どうして？私たちは無意識のうちに大きなθとして大きなOを考えているので。
同様に、我々はまた、無意識のうちに大きなθとして大きなΩを考えてます。
1つの単語、大きなO、大きなθと大きなΩで定義から同じものではありませんが、彼らは私たちの口と脳内に同じものです。
利用制限
るのかを考えてみましょう f(n) > 0 や g(n) > 0 すべての n.でokを考えることで、最速のリアルアルゴリズムによって少なくとも一つの操作が完了し、その執行をしていきたいと思っています。このことは簡単に計算できそうなので利用価値f(n) この絶対値|f(n)|).
f(n) = O(g(n))一般：
f(n) 0 ≤ lim ──────── < ∞ n➜∞ g(n)のための
g(n) = n:f(n) 0 ≤ lim ──────── < ∞ n➜∞ n例:
Expression Value of the limit ------------------------------------------------ n = O(n) 1 1/2*n = O(n) 1/2 2*n = O(n) 2 n+log(n) = O(n) 1 n = O(n*log(n)) 0 n = O(n²) 0 n = O(nⁿ) 0反例に基づ:
Expression Value of the limit ------------------------------------------------- n ≠ O(log(n)) ∞ 1/2*n ≠ O(sqrt(n)) ∞ 2*n ≠ O(1) ∞ n+log(n) ≠ O(log(n)) ∞f(n) = Θ(g(n))一般：
f(n) 0 < lim ──────── < ∞ n➜∞ g(n)のための
g(n) = n:f(n) 0 < lim ──────── < ∞ n➜∞ n例:
Expression Value of the limit ------------------------------------------------ n = Θ(n) 1 1/2*n = Θ(n) 1/2 2*n = Θ(n) 2 n+log(n) = Θ(n) 1反例に基づ:
Expression Value of the limit ------------------------------------------------- n ≠ Θ(log(n)) ∞ 1/2*n ≠ Θ(sqrt(n)) ∞ 2*n ≠ Θ(1) ∞ n+log(n) ≠ Θ(log(n)) ∞ n ≠ Θ(n*log(n)) 0 n ≠ Θ(n²) 0 n ≠ Θ(nⁿ) 0
