O, Omega, Theta

  • Hier mal eine vermutlich dämliche Frage, aber es ist sicher jemand unter Euch, der mir diese beantworten kann. :)


    Wenn ich die Laufzeit einer Funktion in Theta ausdrücke, so betrachte ich eigentlich immer nur die höchste vorkommende Potenz. So ist z.B.


    n² + n + 4 = Theta(n²)


    [hoffe das war soweit richtig.]


    Wie ist das mit den anderen beiden Notationen? Gibt es da eine ähnlich einfache Vorgangsweise?

  • zusätzliche Frage:


    O wird ja als Notation für die obere Schranke,
    Omega für die untere Schranke
    und Theta für die genaue Wachstumsfunktion einer Laufzeitfunktion verwendet.


    Also dachte ich mir, dass man Omega fürs Laufzeitverhalten in BestCase, O für WorstCase und Theta für AverageCase verwendet. Dem scheint aber nicht so. Kann mir wer erklären wann man O, Theta und Omega verwendet?

  • Im Normalfall wird für Laufzeitangaben u.ä. immer Theta verwendet... wenn man in eine Richtung keine Funktion finden kann/will (z.B. bietet sich eine obere Schranke wunderbar an und eine untere ist uninteressant) dann O bzw. Omega.
    Und in der Angabe stehts eh auch immer ;)


    andere Interprettion der Farge - andere Antwort: man die Schreibweisen dann, wenn nur das asymptotische Verhalten gefragt ist... d.h. vor allem bei Laufzeiten. Das ist auch das typische "...das wächst exponentiell/ linear/ quadratisch/..."


    PS: hat wer eine Ahnung, warum man zu O O und nicht Omikron sagt (würd mir nämlich logischer vorkommen)

    Why bother spending time reading up on things? Everybody's an authority, in a free land.

  • bei Theta muss soweit ich weiß sowohl O als auch Omega gelten
    daher die Formel.


    z.B:


    1 :3n^2+4n+3n=O(n2)
    2: durch n^2 durchdividieren
    3: dann ein c wählen sodaß die Behauptung gilt (oder nicht)


    as usual without gewähr :)

    -------------------
    “If you hear hoof beats, you should look for horses, not zebras.”
    --
    "You, Sir, are an Idiot!" - George Hamilton