Groß O Notation
 

Im Internet steht, dass man einen Algorithmus mithilfe der Groß O Notation beschreiben kann, welches einfach ausgedrückt einfach mahematische Funktionen sind. Für was steht aber das n ?

Gelesen habe ich:

,,Abschätzung der Komplexität als Funktion von n"
,,Wachstumsverhalten’ möglichst allgemein” für große n beschreiben(Konstante Faktoren
und Summanden werden nicht berücksichtigt)"

Was ist nun genau n? Und was sagt mir die Steigung aus über den Algorithmus ? Ich habe nur verstanden, dass es irdendetwas mit der Laufzeit des Algorithmus zu tun hat. Freue mich über jede Antwort!

Guck mal hier
[Link nur für registrierte und freigeschaltete Mitglieder sichtbar. Jetzt registrieren...]

Hat das was mit dem Sortialverfahren zu tun? Ala Quicksort, Bubblesort etc. Wobei n für die Anzahl der Zahlen steht. Aus Wikipedia: ,,Anzahl der Elementarschritte in Abhängigkeit von der Größe der Eingangsvariablen". Die Eingangsvariablen stellen meine Zahlen da, die ich am Anfang gegeben habe. Mithilfe der Groß N Notation kann ich nun berechnen wie viel ElementarSchritte ich mit einem Algorithmus z.b. Quicksort brauchen würde um am Ende mein Ergebnis darzustellen. Ist das richtig ?

Die Groß O - Notation wird bei allen Algorithmen verwendet um die Laufzeit eines Algorithmus abzuschätzen. Somit lassen sich Algorithmen, die die gleiche Aufgabe erfüllen schnell miteinander vergleichen. Die Notation ist aber nur ein Richtwert, denn bei der Angabe werden zum Teil sehr (bis zu unendlich) viele Restterme, der Funktion die die Laufzeit eines Algorithmus beschreibt, nicht berücksichtigt. Diese sind aber meist zu vernachlässigen.

Beispiel (Sortieralgorithmus):

O(x^2) heißt das, falls die zu sortierende Liste verdoppelt wird, vervierfacht sich die Laufzeit des Algorithmus ungefähr.

Danke, dann war das was ich gesagt habe zum Teil richtig. Habe es nun verstanden!