Komplexität der Blasensortierung

Und was ist der "durchschnittliche" Wert von n-i ? n/2

Also läuft es in O(n*n/2) , was als O (n ² )

Es gibt verschiedene Arten von Zeitkomplexität - Sie verwenden eine große O-Notation, so dass alle Fälle dieser Funktion mindestens diese Zeitkomplexität aufweisen.

Wenn es sich der Unendlichkeit annähert, kann dies im schlimmsten Fall im Wesentlichen der Fall sein. Die Komplexität der Zeit ist keine exakte Kunst, sondern eher eine Art von Geschwindigkeit, die man für diese Klasse von Algorithmen erwarten kann und daher versuchen Sie, zu genau zu sein.

Zum Beispiel könnte die theoretische Zeitkomplexität sehr gut n ^ 2 sein, obwohl sie theoretisch n * n-1 sein sollte, aufgrund dessen, was auch immer unvorhergesehener Verarbeitungsaufwand sein könnte.

Da die äußere Schleife n-mal läuft und für jede Iteration die innere Schleife (n-i) läuft, kann die Gesamtzahl der Operationen als berechnet werden n * (n-i) = O (n2).

Es ist O (n ^ 2), weil Länge * Länge.