Formelzeichen bei der Laufzeit von Sortieralgorithmen?
Hallo zusammen,
Ich schreibe morgen eine Informatik Klausur über Sortieralgorithmen und wir müssen die Formeln für die jeweilige Laufzeit der verschiedenen Sortieralgorithmen im Best-/Average-/Worstcase Szenario wissen. Allerdings war ich in der Stunde krank und kann mir nicht wirklich erschließen, für was das "O" und das "n" steht. Hat hier wer eine Ahnung davon, da ich im Internet nicht wirklich was hilfreiches finde.
Danke schonmal im Voraus und LG!
1 Antwort
O (Big-O) ist gehört zu den Landau-Symbolen, n ist die Problemgröße.
O(n^2) bedeutet vereinfacht so viel wie: wächst nicht schneller als n^2.
Die Schreibweise wird allgemein für die Komplexität genutzt.
Wenn ich sage die Worstcase Laufzeit des Quicksort liegt in O(n^2), dann bedeutet das, daß die Laufzeit quadratisch in der Problemgröße(=Anzahl der zu sortierenden Elemente) wächst.