誰かがこの質問を理解するのを手伝ってくれますか? 明日の試験でそれがあるかもしれませんが、インターネットや講義で同様の問題を見つけることができません.
質問する
722 次
4 に答える
1
まず、各関数の成長クラス、eG 1、log(n)、n、n log(n) などを決定して、シータ表記を計算する必要があります。そのためには、もちろんそれらの機能を拡張する必要があります。各関数の成長クラスを持っていると、それらをその良さで並べ替える必要があります。最後に、これらの関数を g1 = omega(g2) のようにリレーションに入れる必要があります。したがって、関数 t(n) は、t(n) が g(n) の倍数によって下に制限されている場合、eG n³ >= n² であり、したがって n³ がオメガ(n²)の要素。これは n³ = omega(n²) とも書けます。
于 2013-01-20T14:33:24.983 に答える
1
まず、各関数を として表現する必要がありますTheta(something)。
たとえば、最初のもの: Theta((1-n)(n^3-17)) = Theta(n^4 + ...) = Theta(n^4).
2 番目の場合: Theta(30+log(n^9)) = Theta(30 + 9logn) = Theta(logn).
これらは としてソートされg1, g2ますn^4 = Omega(logn)。
等々。
並べ替えについて:つまり、が少なくとも と同じ速さで成長することをg1 = Omega(g2)意味します。つまり、下限を定義しているということです。したがって、それらを最悪 (最も遅く、最速の成長) から最高 (注意: 演習で「最初のものが最も望ましい」ことを望んでいるのは奇妙ですが、オメガの定義は疑いの余地がありません) に並べ替えます。
ところで: より形式的にしたい場合は、オメガ表記の定義を次に示します
(つまり、f は少なくとも g と同じ速さで成長します)。g1g2f = Omega(g) iff exist c and n0 > 0 such that forall n >= n0 we have 0 <= c*g(n) <= f(n)
于 2013-01-20T14:53:22.693 に答える
1
シータについては、この答えとその答えは、あなたの問題で何が見つかるかを要約しています。そのようなg関数を見つけることができます (たとえば、fは上記の 8 つの関数の 1 つです)。
- fより上で漸近的に一定の境界を掛けたもの( と呼ばれる
O(g(n))) - (通常は) fより下の漸近的な別の定数範囲を掛けたもの(と呼ばれる)
omega(g(n))
たとえば、iv: の場合、 k1.nが下に境界を持ち、k2.nが上に境界を定める2 つの定数を漸近的に簡単に見つけることができるため10^5n、適合します。(ここではfであり、 fとして、簡単なものです)。Θ(n)10^5nO(n)Omega(n)iv.
于 2013-01-20T14:54:44.917 に答える
0
あなたはすべてのビッグOとビッグオメガとビッグシータがより悪い/最良/平均的なケースに適用されることを理解する必要があります
一部の関数の場合：Big O-> O（..）は、この関数が決して超えない上限です。たとえば、大きい値の場合、Big Omega->は、関数がそれを下回ることのない下限です。たとえば、小さい値の場合、Bigthetaはのように：次のような2つの定数があります：Big omega * c <Big Theta <Big O * c2
したがって、サンプルに移動します。i）Big OmegaとO（n ^ + n）の両方でn^4のオーダーです。viii）その定数なので、ObigOとbigOmegaの両方が同じです。したがって、bigThetaは同じです。
于 2013-01-20T15:07:59.950 に答える