Beweisen Sie, wenn h (n)> f1 (n) - f2 (n)> 0 und f1 (n) = Ω (g (n) und f2 (n) = O (g (n)) dann h (n) = Ω (g (n)

-1

ich wie folgt vorgegangen:Beweisen Sie, wenn h (n)> f1 (n) - f2 (n)> 0 und f1 (n) = Ω (g (n) und f2 (n) = O (g (n)) dann h (n) = Ω (g (n)

f1(n) > c1*g(n) , for all n>n1; (*because f1(n) = Ω(g(n))*) 
f2(n) < c2*g(n) , for all n>n2; (*beacuse f2(n) = O(g(n))*) 
Thus, h(n) > c1*g(n) - f2(n) > c1*g(n) - c2*g(n) > (c1 - c2)*g(n), for all n>max(n1,n2)

das Problem für h (n) = Ω (g (n)) Nun ist in Übereinstimmung mit meinem Beweis zu halten, c1 größer sein als c2, bin, weil die Konstanten in der O und Ω-Notation als positiv haben. ich diese Prämisse zu beseitigen nicht in der Lage.

Kann ich jemand helfen mit, dass Sie mir bitte. Danke

Quelle

2016-09-05 PSuniq

** eklatant off-topic ** (diese Frage hat nichts mit Programmierung zu tun) – xenteros

Ich stimme diese Frage als off-topic zu schließen, weil es kein tatsächliches Codeproblem ist. – Fildor

Ich verstehe nicht, was Big-O-Notation ist? Bitte weisen Sie darauf hin, welche Aussage in meiner Frage der formalen Definition von Big-O widerspricht. Ich wäre dir immer dankbar. Auch ich dachte Zeit - Komplexitätsberechnung bezieht sich ziemlich auf Programmierung! "Eklatant" scheint dort nur hart zu sein! – PSuniq

die Erklärung sieht nicht richtig auf ich.

Lassen Sie g(n)=n, f1(n)=n+1, f2(n)=n und h(n)=2. Dann 2 > 1 > 0 hält, aber h(n) ist offensichtlich nicht Ω (n).

Quelle

2016-09-05 12:17:13 Gassa

Also ja, diese Prämisse kann dann nicht beseitigt werden. Das Beispiel, das Sie mir gegeben haben, ist genau ein Fall, in dem c1 <= c2 und daher für h (n) = Ω (n), einige c1 und c2 müssen existieren, so dass c1> c2. Vielen Dank. – PSuniq

Beweisen Sie, wenn h (n)> f1 (n) - f2 (n)> 0 und f1 (n) = Ω (g (n) und f2 (n) = O (g (n)) dann h (n) = Ω (g (n)

Antwort

Verwandte Themen