Verständnisprobleme bei der O-Notation

[mittelding]

Hallo!

Zuerst einmal muss ich sagen, dass das Thema "Algorithmen" bei uns im Studiengang Medieninformatik nicht so arg in die Tiefe geht wie das vllt. in der reinen Informatik der Fall ist, ein grobes Verständnis für das ganze ohne großen Tiefgang reicht also völlig aus.

Es geht bei uns lediglich um Zeitkomplexität, nicht um Speicherplatz.
Anhand dem Verlauf der Vorlesungen konnte ich bis jetzt aber keine klare Linie erkennen, wie die Notation tatsächlich zu bestimmen ist.

Was bisher geschah:

Erst ging es immer darum, den worst case, average case und best case eines Algorithmus zu bestimmen. Bei Sortierverfahren wurde aber getrennt zwischen Vergleichen (Comparisons) und Bewegungen (Moves) - soweit leuchtet das auch ein.
Plötzlich ging es dann aber mit "Größenordnungen der Komplexität" weiter, und damit kam die O-Notation.

Da wäre ich auch bei der ersten Frage: mir ist völlig unklar, inwieweit wort/avg/best case mit der O-Notation zusammenhängen, oder ob sie es überhaupt tun.
Im Skript gibt es eine Liste mit typischen Größenordnungen, wie z.B. log n, n, n log n, n², n^k und 2^n und auch ein Beschreibungstext, welcher jeder dieser Ordnungen ein typisches Beispiel verpasst.
Bis zu diesem Punkt bin ich davon ausgegangen, dass die 3 cases mit der Größenordnung erstmal nichts zu tun haben.

Jetzt wird an einer Stelle aber doch plötzlich der Bezug zu den 3 cases hergestellt. Zitate:

"Die Größenordnung eines Komplexitätsmaßes kann für die Relativierungen worst case, best case, average case unterschiedlich sein."

"Im Beispiel xy ist die Größenordnung von f im best case O(1) und im worst sowie average case O(n)."

"Ist das Komplexitätsmaß f(n) ein Polynom, so wird die Komplexität durch die höchste Potenz bestimmt."

Momentan werde ich daraus nicht schlau. Heißt das, man gibt für alle 3 fälle unterschiedliche "O's" an oder wie? Und was ist mit Moves und Comparisons bei Sorterverfahen, muss man hier nochmal aufteilen in M und C?

Etwas Aufklärung wäre super. Die Fragen sind denke ich mal das wichtigste bevor es weitergeht, aber am Ende wäre natürlich die Frage, wie man vorgeht um aus einem gegebenen Stück Code die O-Notation herauszubringen.

Vielen Dank!

[Monger]

Siehe hierzu:
http://de.wikipedia.org/wiki/Landau-Symbole

In der Komplexitätstheorie lassen sich die verschiedenen Probleme und Algorithmen dann folgendermaßen vergleichen: Man kann für Problemstellungen mit Ω eine untere Schranke für beispielsweise die asymptotische Laufzeit angeben, mit O entsprechend eine obere Schranke. Bei wird die Form von f (z. B. f(n) = n2) auch als die Komplexitätsklasse oder Aufwandsmaß bezeichnet (also z. B. quadratisch).

Sprich: mathematisch gesehen ist das O Kalkül immer der Worst Case. Die anderen beiden Notationen nutzt (zumindest in der Informatik) kaum einer, weil der Best Case sowieso nicht interessiert (wie schnell es wirklich läuft, ist meistens nicht so spannend. Hauptsache, es läuft schnell genug), und der Average Case verlangt, dass man gewisse Annahmen über die Daten macht, die mit diesem Algorithmus bearbeitet werden. Das ist oft genug gar nicht vernünftig machbar, deshalb geht man lieber gleich vom Worst Case aus.

[Nasenbaer]

Monger hat Recht. Eigentlich nutzt man unterschiedliche Symbole für die 3 Fälle und das O eigentlich nur für den worst case, der nicht selten ja auch der interessanteste ist um für den eigenen Algorithmus abschätzen zu können ob er auch im schlimmsten Fall brauchbar ist. (Es gibt allerdings auch so manchen Algorithmus der im worst case saulahm ist aber für die meisten Aufgaben für die er zur Anwendung kommt sehr gut arbeitet und damit einen guten Average case besitzt.)


Wenn du jetzt beispielsweise nen Alrotihmus xy hast und willst dessen Komplexität bestimmen dann kannst du das so machen:


function f()
{
int max = 9;
int result[100];

For (int y=0; y < max; y++ )
{
For (int x=0; x < max; x++ )
{
result[y*10+x] = bla(x,y);
}
}
}


So hier sind worst, average und best case identisch wie man sieht, wenn die Komplexität von bla() nicht von x und y abhängt (z.B. falls die Funktion nur das Produkt aus x und y berechnet). Damit gilt:

f € O(max * max * O(bla)) = O(max^2 * O(bla)) = O(max^2), falls bla € O(1)
(€ soll hier das "Element von"-Symbol, das kleine Epsilon sein :D )

Für dein Sortierbeispiel ist damit eigentlich nur zu sagen, dass man Comparisions und Moves nur dann unterscheiden muss wenn sie eine unterschiedliche Komplexität haben also z.B. Moves € O(n^2) und Comparisions € O(n).
Eigentlich gehören aber beide Operationen zu O(1), denn ein Move mit Ziwschenspeicherung braucht 3 Anweisungen und ein Vergleich braucht eine. Da man bei Polynomen die höchste Potenz nimmt (hier jeweils 0) ist das Ergebnis für beide Operation, dass sie in O(1) liegen. (Falls das in der Vorlesung bisher nicht deutlich wurde die O-Notation beschreibt Mengen in den Funktionen gleichen Komplexitätsgrades liegen.


P.S.: Ich hoffe ich hab das alles richtig erklärt. Ist schon ne Weile her. :)

[AlecWhite]

O beschreibt die obere asympotische Schranke - oder übersetzt: Wohin geht die Richtung wenn n gegen unendlich geht.