Was ist die zeitliche Komplexität dieser Blasensortierfunktion?

Question

Ich schrieb diese Bubble-Sort-Funktion, aber ich habe eine harte Zeit herauszufinden, die Zeit Komplexität davon.

function bubbleSort(items) { 
    for (var i = items.length; i > 0; i--) { 
     for (var j = 0; j < i; j++) { 
     if (items[j] > items[j + 1]) { 
      var temp = items[j]; 
      items[j] = items[j + 1]; 
      items[j + 1] = temp; 
     } 
     } 
    } 

    return items; 
} 

Ich weiß, dass die äußere Schleife Zeit Komplexität von O (n) hat. Aber was ist die zeitliche Komplexität der inneren Schleife (da sie bei jedem Durchgang ein Element weniger von items durchläuft)?

Answer 1

Die innere Schleife ist O (n). Zu Beginn wird es n mal ausgeführt, am Ende 1 mal. Im Durchschnitt wird es n/2 mal ausgeführt. Konstante Faktoren spielen keine Rolle, das ist O (n).

Zusammen ergibt sich daher die Gesamtlaufzeit O (n).

Answer 2

Wenn man bedenkt, wie oft innere Schleife ausgeführt wird, können Sie eine bessere Idee:

1st run : N times, 
2nd run: N-1 times 
... 
Nth run: 1 time. 

Wenn Sie sie alle

N + (N-1) + (N-2) + ... + 1 = [N * (N+1)]/2 

mal hinzufügen. Das macht O (N^2). Für weitere Informationen besuchen Sie diese Antwort hier: https://stackoverflow.com/a/29556003

Answer 3

Eine Möglichkeit, die Zeitkomplexität des Algorithmus zur Berechnung zu beachten, dass die innere Schleife i Iterationen wo i reicht von n bis zu 1 ausführt (wobei n die Länge der ist Eingang). Das bedeutet, dass wir eine Summierung tun können, um die Gesamtzahl der Schritte im Algorithmus zu erhalten:

n + (n-1) + ... + 3 + 2 + 1 

Diese Summe eine vertraute geschlossene Formel hat:

n*(n+1)/2 

Diese Formel deutlich O(n^2) ist.