O, Omega, Theta
Results 1 to 6 of 6

Thread: O, Omega, Theta

  1. #1
    Irrlicht's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    208
    Thanks
    0
    Thanked 1 Time in 1 Post

    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?

  2. #2

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    247
    Thanks
    0
    Thanked 0 Times in 0 Posts
    bei der oberen und unteren grenze funzt das genauso

  3. #3
    Irrlicht's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    208
    Thanks
    0
    Thanked 1 Time in 1 Post
    ok, *dank*

  4. #4
    Irrlicht's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    208
    Thanks
    0
    Thanked 1 Time in 1 Post
    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?

  5. #5
    jeuneS2's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Posts
    547
    Thanks
    1
    Thanked 45 Times in 29 Posts
    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.

  6. #6
    wolfmann's Avatar
    Title
    Baccalaureus
    Join Date
    Mar 2002
    Location
    in-between
    Posts
    524
    Thanks
    3
    Thanked 6 Times in 4 Posts
    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


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •