[Theor. Inf.] Symbole bei Laufzeitberechnung

[Phoenix]

Hi,

kann sein, das das die falsche Sparte ist, aber zu Klatsch und Tratsch würde ich das Problem jetzt doch nicht stecken wollen. Hat zwar weniger mit Programmieren an sich zu tun, aber dennoch ne Menge mit den Theoretischen Grundlagen.

Aaaaalso:

Es gibt bei Angaben zur Laufzeit folgende Symbole: Omega, Omikron und Theta. Die bedeuten das ein Durchlauf eines Algorithmus mindestens, höchstens oder ca. (? wirklich? da fängts schon an..) eine bestimmte Zeit in Anspruch nimmt.

Die Frage: Welches Symbol steht für was genau und wie werden diese Symbole korrekt abgekürzt (um in einer Klausur nächste Woche nicht das richtige zu meinen und das falsche Hinzuschreiben )?

Hat jemand zu dem Thema 'Wie berechne ich die Laufzeit von Algorithmen im average, best oder worst case'? vielleicht auch noch gute Links dazu, so das ich mir das Lernen etwas vereinfachen kann?

[tr909]

Das haben wir kürzlich auch gemacht.

Hier mal ein link.

http://www.in.tu-clausthal.de/~horma...18.11.2004.pdf (Seite 13)
(Das O scheint das von dir angesprochene Omikron zu sein, wobei ich mich hier nicht festlegen will )

Evtl hilft dir das schon mal. Die anderen links muß ich nochmal rauskramen.



Gruß
tr909

[Phoenix]

Ach Du schande, steht das da kompliziert drin.

Aber nochmal kurz, um zu sehen ob ich das wirklich verstanden habe:

• O wird verwendet, wenn eine Ausführung mindestens so lange braucht (obere Grenze),
• Omega wird verwendet, wenn eine Ausführung höchstens so lange braucht (untere Grenze), und
• Theta wird verwendet, wenn die obere und untere Grenze (also O und Omega) gleich sind.

Ist das so korrekt?

[tr909]

so quasi.
im alg. benutzen wir eigentlich nur die O-Notation, also das schlechteste Laufzeitverhalten zum vergleichen von Algorithmen, weil der schlechteste Fall trifft ja doch häufiger ein (z.B. sortieren von in umgekehrte Reihenfolge sortierten Folgen )

Gruß
tr909

[Binärbaum]

@phoenix:

Also wir haben das anders gelernt:

• Groß-O gibt die worst-case-Komplexität an (obere Schranke)
• Omega gibt die best-case-Komplexität an (untere Schranke) und
• Theta steht für die genaue Komplexität, d.h. Omega= Groß-O = Theta

MfG
Binärbaum

[Phoenix]

Zitat von Binärbaum:

Also wir haben das anders gelernt:

• Groß-O gibt die worst-case-Komplexität an (obere Schranke)
• Omega gibt die best-case-Komplexität an (untere Schranke) und
• Theta steht für die genaue Komplexität, d.h. Omega= Groß-O = Theta

Ähh? Also entweder bin ich blind, oder Du hast genau das gleiche geschrieben wie ich oben?¿?

[Binärbaum]

Zitat von Phoenix:

Zitat von Binärbaum:

Also wir haben das anders gelernt:

• Groß-O gibt die worst-case-Komplexität an (obere Schranke)
• Omega gibt die best-case-Komplexität an (untere Schranke) und
• Theta steht für die genaue Komplexität, d.h. Omega= Groß-O = Theta

Ähh? Also entweder bin ich blind, oder Du hast genau das gleiche geschrieben wie ich oben?¿?

Nein, der worst-case (Groß-O) gibt an, wie lange ein Algorithmus höchstens braucht, während best-case (Omega) die Minimallaufzeit eines Algorithmus angibt. Bei dir steht es genau umgekehrt.

MfG
Binärbaum

[Phoenix]

Also wäre es dann so korrekt:

• O wird verwendet, wenn eine Ausführung mindestens höchstens so lange braucht (obere Grenze),
• Omega wird verwendet, wenn eine Ausführung höchstens mindestens so lange braucht (untere Grenze), und
• Theta wird verwendet, wenn die obere und untere Grenze (also O und Omega) gleich sind.

Oder?

Edit: BBCode korrigiert. Wer rechnet denn auch damit das das default-Tag 'strike' hier nur 's' heisst?

[Binärbaum]

Genau so ist es!

MfG
Binärbaum