さて、ここで2つの質問があります:-
f(n) が成長率を求める関数である場合、 f(n)=O(g(n)) の場合と同様に、オメガとシータの場合のように、3 つの表記法すべてで g(n) は同じになります。 ?
シータ表記は「オメガとオー」ですが、場合によっては、オーとオメガ関数が異なる場合、そこにシータ関数をどのように見つけるのでしょうか? ありがとう ：）
質問する
1522 次
2 に答える
4
O、Θ、および Ω 表記法は、関連するが非常に異なる概念を表します。O表記は、関数の成長率の漸近的な上限を表します。それは、関数が最終的に他の関数の定数倍数によって上から制限されることを示しています。Ω表記も同様ですが、下限を示します。Θ 表記は、漸近的なタイト バウンドを提供します。入力が十分に大きい場合、アルゴリズムは、関数の定数倍数によって上と下の両方から制限される速度で成長します。
f(n) = O(g(n)) の場合、f(n) = Ω(g(n)) または f(n) = Θ(g(n))であるとは限りません。たとえば、1 = O(n) ですが、n は 1 より厳密に速く成長するため、1 ≠ Ω(n) です。
f(n) = O(g(n)) および Ω(h(n)) (g(n) ≠ h(n)) であることがわかった場合、関数 j を決定するために、より正確な分析を行う必要がある場合があります。 (n) f(n) = Θ(j(n)) となります。g(n) = Θ(h(n)) の場合、f(n) = Θ(g(n)) と結論付けることができますが、上限と下限が異なる場合、Θ を決定する機械的な方法はありません。関数の成長率。
お役に立てれば！
于 2012-05-07T18:51:11.517 に答える
1
f（n）= O（g（n））は、n> N => | f（n）|≤C| g（n）|を意味します。一部の定数NおよびCの場合。
f（n）=Ω（g（n））は、n> N => | f（n）|≥C| g（n）|を意味します。一部の定数NおよびCの場合。
f（n）=Θ（g（n））は、f（n）= O（g（n））およびf（n）=Ω（g（n））を意味します。
gを「良い」関数（つまり、n ^ r * Log（n）^ s）にしたい場合、すべてのfがf（n）=Θ（g（n））のようなagを見つけることはできません。 。たとえば、f（n）= cos（n）²* n + sin（n）²*n²の場合、f（n）= O（n²）およびf（n）=Ω（n）となりますが、 t f（n）=Θ（g（n））となるような「良い」gを見つけます。
于 2012-05-07T19:36:07.767 に答える