g = O(f) und umgekehrt ....

andyy · Anmeldungsdatum: 30.04.2006 Beiträge: 6

Hallo Leute,

in der Hoffnung, daß irgendwann mal irgendjemand auf eine meiner Fragen antwortet, eine einfache Frage.

Es geht um die O-Notation und das

.

Und zwar benutzt man die O-Notation ja, um eine obere Schranke darzustellen, die man naturgemäß möglichst niedrig ansetzen will. Kein Mensch würde freiwillig "Der Algorithmus hat eine Laufzeit von

schreiben, wenn er mit log n auskommt. Klar.

Beim Omega ist es aber anders, denn ich kann immer noch "runter" gehen, und dann sehen meine Ergebnisse noch besser aus.

Angenommen, ich habe

. Dann kann ich auch genauso gut

oder wenn ich will sogar

schreiben, ohne zu lügen.

Ist das "zulässig"?

Ich meine, beim Groß O will jeder etwas möglichst kleines als "Worst Case" angeben. n^2 anstatt n würde niemand freiwillig machen.

Nur kann man beim Omega immer noch weiter runtegehen.

Wie weit darf ich nach unten abschätzen, ohne das das Ergebnis verfälscht wird?

Bitte antworte wenigstens dieses mal jemand. Das würde mich echt froh Tanzen

machen.

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

Es geht bei den Landau-Symbolen nicht nur darum Algorithmen zu bewerben, sondern darum Laufzeiten sinnvoll zu beschreiben.

Natuerlich kannst du sagen

, aber die Aussage ist ziemlich gering. Aehnlich wie 5 < 42 oder "Manchmal ist Wasser nass."

Und wenn du wissen willst wie gut ein Algorithmus ist schaust du am besten auf die obere Schranke und nicht auf die untere :)

andyy · Anmeldungsdatum: 30.04.2006 Beiträge: 6

Danke für die schnelle Antwort!!

Algorithmus bewerben ... das ist witzig. smile

Ich habe hier einen Fall, bei dem der Autor herausgefunden hat, daß die Laufzeit

ist.

Dann sagt er, das ist

und schließlich

.

Ich frage mich, ob das nicht zu großzugüig abgerundet ist, nach dem Motto wenn es groöer als 42 ist, ist es auch größer als 5 (wie Du sagtest).
Wieviel Aussage hat das Omega überhaupt, wenn ich so lange nach unten gehen kann, bis das Ergebnis cool aussieht?

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Das hängt doch immer vom Kalkül des Autors ab. Wenn man die genaue asymptotische Beschreibung will, muss man wohl

nehmen.

Stellen wir uns mal vor wir haben einen Algorithmus, der tatsächlich eine Zeitkomplexität

hat. Um nun aber zu beweisen, dass er in polynomialer Zeit durchlaufen werden kann, würde sich keiner die Mühe machen

zu beweisen, wenn z.B.

trivial wäre. Es kommt also immer auf die Aussage an, die man tätigen will.

Genauso wie die obere Schranke immer weiter vergrößert werden kann, kann die untere Schranke meist noch ganze Klassen runtergeschraubt werden.
Das "großzügige" Runden wird ja auch in der Analysis oft gemacht um einfachere Terme zu erhalten. Insofern solltest du dich über

freuen.

andyy · Anmeldungsdatum: 30.04.2006 Beiträge: 6

Da hast Du recht! Ich habs jetzt begriffen.

Danke für die Antwort,

Sebi Wink