O-Notation-Beweisen?
Kann mir jemanden erklären, wie man das löst?
1 Antwort
Das kommt darauf an, ob man die Aussage belegen oder widerlegen will.
Zum Belegen nimmt man für f und g allgemeine Funktionen und versucht so aus den Eigenschaften links logisch die eigenschaften rechts herzuleiten.
Zum Widerlegen reicht es, spezielle f und g zu finden, für die die Aussage nicht gilt.
Probier also erstmal paar Funktionen aus und schaue, ob die Aussage wohl richtig ist oder nicht.
Generell ein nützlicher Zusammenhang für Überlegungen:
Hier mal ein Beispielbeweis: Seien f, g beliebige Funktonen auf den natürlichen Zahlen. Angenommen es gelte:
Also die Aussage impliziert, dass immer wenn die linke Seite erfüllt ist, dann auch die rechte Seite erfüllt ist. Für f(n) = n und g(n) = n log n ist die linke Seite nicht erfüllt (der Schnitt ist leer). Daher ist dieser Fall nicht hilfreich zur Überprüfung der Aussage.
Für f(n) = g(n) = n gilt sowohl rechts als auch links. Damit die Aussage wahr ist, muss das aber für alle Funktionen gelten, die die rechte Seite erüllen.
Ich bin mal so frei und spoilere, dass es f und g gibt, die links erfüllen, rechts aber nicht, womit die Aussage falsch ist. Diese musst du nun nur noch finden.
Warte warum ist der Schnitt zw. n und nlogn leer. n wächst doch langsamer als nlogn, aber nicht gleich schnell.
Aber mit Hilfe des Internets kam ich auf f(n) = n und g(n) = n sin(n). Das sollte passen.
O(n) enthält alle Funktionen, die lamgsamer wachsen als n. Omega( n log m) hingegen alle, die schneller wachsrn als n log n, was wiederum schneller wächst als n.
Es gibf aber keine Funktionen, die lamgaamer als n und schneller als n log n eachsrn. Desjalb ist der Schnitt leer.
Auch dein letztes Beispiel beweist oder widerlegt die Aussage nicht. Schau dir aber mal f(n) = n und g(n) = 1 an.
Aso ja dann hab ich alles falsch verstanden sorry. Ich hab die Landau Symbole verteilt und gemischt und daraus neue gemacht wie man das am Anfang des Studiums lernt. Ich glaub das hieß Satz von Demorgens oder sowas. Auf jeden Fall war das der Fehler.
Hey ich weiß es ist sehr lange her, aber ich wollte kurz mal fragen, ob diese Aussage ungültig bleibt, auch wenn der Schnitt vertauscht wird und f in Omega, Theta oder O von g liegt?
2 Tage sind nicht so lang find ich :D
Mit umgekehrten Implikationspfeil ist die Aussage wahr. f ist immer in O(f) und Theta(g) ist immer Teilmenge von Omega(g). f liegt alao in beiden, deshalb ist der Schnitt nicht leer.
Nein nicht so meinte ich. Das wäre zu einfach...
Ich meinte macht das nen Unterschied, wenn man O(f) Schnitt Omega(g) macht oder umgekehrt?
Und dazu kommt f(n) in O(g) oder Omega(g), weil Theta(g) schon die beiden enthalten.
Da bleibt immer, was man da tut, die Aussage falsch
Ah, ok ich hoffe mal, dass ichs jetzt verstanden hab.
Die Reihenfolge des Schnittes kannst du vertauschen, da der Durchschnitt eine symmetrische Operation ist.
Erstetzr man rechts Theta(g) durch Omega(g), dann ist die Aussage wahr. Für O(g) bleibt sie falsch.
Ja genau so meinte ich, aber wieso funktioniert es für Omega(g). Letztendlich kann man f=1 und g=n nehmen und dann gikt das nicht oder?
Doch, das gilt dann auch. 1 ist links in beiden Mengen enthalten und rechts ist f=1 in Omega(1). Für das Beispiel gilt es sogar auch für Theta und O.
Vergiss nicht, dass die großen Buchstaben keine strikten Schranken beschreiben. Gleiches asymptotisches Wachstum ist auch zugelassen.
Ah sorry, hab g=1 gelesen statt n.
Dann ist der Schnitt links leer. In dem Fall ist die Aussage immer wahr, egal was rechts ist.
Ich dachte aber, wenn man das mit Theta falsch bewiesen hat, dann gilt das nicht für alle anderen. Nun dieses Beispiel funktioniert auch für Theta. Bin verwirrt jetzt 😅
Genau, das Beispiel geht auch für Theta (hoffe du hast die Korrektur gesehen).
Damit die Aussage wahr ist, sprich allgemeingültig, muss sie für alle f, g gelten. Einzelne Beispiele belegen sie nicht.
Ah okay alles gut!
Ich meinte für Omega(f) und O(g) mit f=1 und g=n ist die Menge nicht leer und dann gilt recht f ist in Omega(g) ne? Ich glaub ich hab das nicht so konkret dargestellt. Dieser Fall ist den, was Sie meinten, was nur gilt ne?
Vergessen Sie, was ich da geschrieben hab, das war n Denkfehler. Da muss man, wenn die Aussage stimmt sie mathemathisch beweisen glaub ich und nicht durch ein Beispiel, aber kann man das machen?
Hab mal einen Beispielbeweis in meiner Antwort ergänzt. Vielleicht hilft dir das ja.
Eigentlich hab ich nicht so viel verstanden. Können Sie etwa mehr dazu sagen?
Ja.
Also erstmal repräsentieren die Landau-Symbole ja Mengen von Funktionen. Die Mengen enthalten alle Funktionen, welche mindestens genauso schnell (Omega), bzw. genauso schnell (Theta), bzw. höchstens genauso schnell (O) wachsen wie eine Funktion f.
Der Durchschnitt von zwei Mengen ist wieder eine neue Menge. Diese enthält alle Elemente, welche Elemente von beiden Mengen sind. Wenn die Menge nicht leer ist (also der Durchschnitt), dann muss mindestens eine Funktion darin liegen. Insbesondere liegt diese auch in beiden einzelnen Mengen (O(f) und Omega(g)). Wir nennen sie einfach mal h.
Da sie in O(f) liegt, wächst sie höchstens so schnell wie f.
Omega(g), enthält alle, die schneller als g wachsen. Zudem enthält sie dieses h. Da f auch schneller wächst als h, also auch als g, muss f auch darin liegen.
Also ich habs so verstanden und die Gleichung gelöst und da hatte ich: O(f(n)) geschnitten mit Theta(g(n)) und daraus folgt, dass f(n) im Theta(g(n)) liegt.
Für f(n) = n und g(n) = n soll die Aussage gelten.
Aber für f(n) = n und g(n) = n log n soll das nicht gelten