0 Daumen
381 Aufrufe

Frage:

Meine Aufgabe besteht darin Ungleichungen mit O-Notation zu beweisen.Als Hinweis ist gegeben:

Zu einem korrekten Beweis für O(f(n)) <= O(g(n)) gehört die
Angabe einer Konstante c > 0 und eines N (Element der natürlichen Zahlen), sodass für alle n >=N gilt: f(n) <= c · g(n).

Als Bsp einer der Aufgaben:

O(log(n)) <= O(n^(1/2))

--> laut Internetrecherche mit Induktion mögl. oder mit Abschätzungen

Problem ist, dass ich nicht so ganz verstehe wie die Reihenfolge des Beweis sein sollte und wie man c und N wählt.

Kann mir Jemand auf die Sprünge helfen?

Avatar von

1 Antwort

0 Daumen

Schau dir die Graphen der beiden Funktionen an.

Avatar von 5,6 k

Hab ich gemacht, aber was soll das mir bei diesen beiden Funktionen groß bringen? Weil n^(1/2) ist immer überhalb von log(n).

Was soll man dann für N und c wählen? Oder ist das dann egal, weil dann die Ungleichung immer gilt?

Weil n1/2 ist immer überhalb von log(n).

\(N = 0, c = 1\).

Oder ist das dann egal, weil dann die Ungleichung immer gilt?

Mathematisch betrachtet ist es egal.

Praktisch gesehen musst du natürlich noch beweisen, dass tatsächlich

        \(\log n \leq c\cdot n^{\frac{1}{2}} \quad \forall n>N\)

ist. Und da könnte es sinnvoll sein, ein größeres \(N\) zu wählen oder ein anderes \(c\).

Kannst anhand von dieser Aufgabe: O(2^n) <= O(n!) mir zeigen wie der Beweis aussehen würde? Weil irgendwie verstehe ich nicht, wie c und N wählen soll, also ich verstehe nicht auf was man da ahten soll.

anhand von dieser Aufgabe: O(2n) <= O(n!)

\(N = 4, c=1\)

wie c und N wählen soll, also ich verstehe nicht auf was man da ahten soll.

Darauf dass der Graph von \(n!\) für \(n>N\) über dem von \(2^n\) verläuft.

Falls das nicht hinhaut, dann nimmt man ein größeres \(c\). GeoGebra hat dazu Schieberegler.

Okay so ist das also gemeint. Und den Beweis mit Induktion zu machen sollte dann passen, oder?

Ja, sollte passen.

Okay super, Danke für deine Mühe :)

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community