Ich versuche Bubble sort. Es gibt 5 Elemente und das Array ist unsortiert. Der schlechteste Fall für die Blasensortierung sollte O (n ^ 2) sein.
Als Beispiel verwende ich
A = {5, 4, 3, 2, 1}
In diesem Fall sollte der Vergleich 5 ^ 2 = 25 sein. Mit der manuellen Verifizierung und dem Code erhalte ich eine Vergleichszahl von 20. Im Folgenden finden Sie den Bubble-Sort-Implementierungscode
%Vor%Die Ausgabe folgt
Irgendeine Idee, warum die Mathematik nicht 25 sein wird?
Die Big-O-Notation sagt nichts darüber aus, wie viele Iterationen (oder wie lange) ein Algorithmus dauert. Dies ist ein Hinweis auf das Wachstum rate einer Funktion, wenn die Anzahl der Elemente zunimmt (normalerweise gegen unendlich).
In diesem Fall bedeutet O (n 2 ) einfach, dass die Berechnungsressourcen der Blasensorte um das Quadrat als Anzahl der Elemente wachsen. Also, wenn Sie doppelt so viele Elemente haben, können Sie erwarten, dass es (schlimmstenfalls) 4-mal so lange dauert (wie eine obere Grenze). Wenn Sie 4-mal so viele Elemente haben, erhöht sich die Komplexität um den Faktor 16. Etc.
Für einen Algorithmus mit O (n 2 ) -Komplexität könnten fünf Elemente 25 Iterationen oder 25.000 Iterationen benötigen. Es gibt keine Möglichkeit zu sagen, ohne den Algorithmus zu analysieren. In gleicher Weise könnte eine Funktion mit O (1) -Komplexität (konstante Zeit) 0,000001 Sekunden zur Ausführung oder zwei Wochen zur Ausführung benötigen.
Wenn ein Algorithmus n^2 - n -Operationen akzeptiert, wird dies immer noch auf O(n^2) vereinfacht. Die Big-O-Notation ist nur eine Annäherung an die Skalierung des Algorithmus und nicht eine exakte Messung, wie viele Operationen für eine bestimmte Eingabe erforderlich sind.
Betrachten Sie: Ihr Beispiel, bubble-sorting 5 Elemente, nimmt 5x4 = 20 Vergleiche. Das Verallgemeinern von N Elementen zur Blasensortierung erfordert N x (N-1) = N ^ 2 - N Vergleiche, und N ^ 2 erhält sehr schnell eine LOT, die größer als N ist. Hier kommt O (N ^ 2) her. (Für 20 Elemente sehen Sie beispielsweise 380 Vergleiche.)
Bubble sort ist ein spezieller Fall und seine volle Komplexität ist (n * (n-1)) - was Ihnen die richtige Anzahl gibt: 5 Elemente führen zu 5 * (5-1) Operationen, die 20 ist, und was Sie im schlimmsten Fall gefunden haben.
Die vereinfachte Big O-Notation entfernt jedoch die Konstanten und die am wenigsten signifikant wachsenden Terme und gibt nur O ( n ^ 2). Dies macht es leicht, es mit anderen Implementierungen und Algorithmen zu vergleichen, die nicht genau (n * (n-1)) haben, aber wenn es vereinfacht wird, zeigt sich, wie die Arbeit mit einer größeren Eingabe zunimmt.
Es ist viel einfacher, die Big-O-Notation zu vergleichen, und bei großen Datasets sind die Konstanten und die kleineren Terme vernachlässigbar.
Denken Sie daran, dass O (N ^ 2) vom tatsächlichen Ausdruck von C * N (2) vereinfacht ist; das heißt, es gibt eine beschränkte Konstante. Für Bubble-Sort wäre C zum Beispiel ungefähr 1/2 (nicht genau, aber nahe).
Ihre Vergleichszahl ist auch aus, ich denke, es sollten 10 paarweise Vergleiche sein. Aber ich denke, Sie könnten erwägen, Elemente zu tauschen, um eine andere zu sein. So oder so ändert sich nur die Konstante, nicht der wichtigere Teil.