Selectionsort arbeitet über die Indizes im Array; Für jeden Index ruft Selectionsort indexOfMinimum und swap auf. Wenn die Länge des Arrays n ist, dann gibt es n Indizes im Array.
Da jede Ausführung des Körpers der Schleife zwei Zeilen Code benötigt, könnte man denken, dass 2, n Zeilen Code durch Selectionsort ausgeführt werden. Aber es ist nicht richtig, denn indexOfMinimum undswap sind Funktionen: Jede von ihnen enthält weitere Codezeilen.
Wie viele Zeilen Code werden bei einem einzigen Aufruf vonswap ausgeführt? In einer normalen Implementation sind es drei Zeilen Code. Daher ist die Laufzeit jedes Aufrufs von swap konstant.
Wie viele Zeilen Code werden bei einem einzigen Aufruf von indexOfMinimum ausgeführt? Wir müssen dazu die Schleife in indexOfMinimum betrachten. Wie oft wird diese Schleife während eines Aufruf von indexOfMinimum durchlaufen? Das hängt von der Größe des Subarrays ab. Wenn das Subarray das ganze Array ist (wie es im ersten Schritt der Fall ist), läuft der Schleifen-Körper n mal. Wenn das Subarray von der Größe 6 ist, dann läuft der Schleifen-Körper 6 mal.
Nehmen wir an, das Array ist von der Größe 8. Wir analysieren im folgenden wie Selectionsort funktioniert.
  1. Beim ersten Aufruf von indexOfMinimum muss jeder Wert im Array betrachtet werden, so dass der Schleifen-Körper in indexOfMinimum 8 mal läuft.
  2. Im zweiten Aufruf von indexOfMinimum muss er jeden Wert im Subarray mit den Indizes 1 bis 7 betrachten, und so läuft der Schleifen-Körper in indexOfMinimum 7 mal.
  3. Im dritten Aufruf betrachtet er das Subarray mit den Indizes 2 bis 7; Der Schleifen-Körper läuft 6 mal.
  4. Im vierten Aufruf werden die Indizes 3 bis 7 betrachtet; Der Schleifen-Körper läuft 5 mal.
  5. Im achten und letzten Aufruf von indexOfMinimum läuft der Schleifen-Körper nur 1 mal.
Wenn wir die Wiederholungen des Schleifen-Körper vonindexOfMinimum addieren, erhalten wir 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 Wiederholungen.

Hinweis: Berechnung der Summe der Zahlen von 1 bis n

Wie berechnen wir schnell die Summe 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1? Hier ist ein Trick. Zuerst addieren wir die größte und die kleinste Zahl, also 8 + 1 = 9. Dann addieren wir die zweitgrößte und die zweitkleinste Zahl: 7 + 2 = 9. Auch 6 + 3 resultiert in 9 und ebenso 5 + 4 = 9. Damit erhalten wir:
(8+1)+(7+2)+(6+3)+(5+4)=9+9+9+9=49=36 . \begin{aligned} (8 + 1) + (7 + 2) + (6 + 3) + (5 + 4) &= 9 + 9 + 9 + 9 \\ &= 4 \cdot 9 \\ &= 36 \ . \end{aligned}
Es gab vier Zahlenpaare deren Addition jeweils 9 ergab. Hier ist die allgemeine Vorgehensweise, um jede Folge von aufeinanderfolgenden Ganzzahlen zu addieren:
  1. Addiere die kleinste und die größte Zahl.
  2. Multipliziere das Ergebnis mit der Anzahl der Paare.
Was passiert, wenn die Anzahl der ganzen Zahlen in der Sequenz ungerade ist, so dass eine Zahl nicht gepaart werden kann? Betrachte einfach die ungepaarte Zahl in der Mitte der Sequenz als ein halbes Paar. Als Beispiel wollen wir 1 + 2 + 3 + 4 + 5 bestimmen. Wir haben zwei volle Paare (1 + 5 und 2 + 4, deren Summe jeweils 6 ist) und ein "halbes Paar" (3, das ist die Hälfte von 6), was insgesamt 2,5 Paare ergibt. Wir multiplizieren 2, comma, 5, dot, 6, equals, 15, und erhalten die richtige Antwort.
Allgemein ausgedrückt für eine Sequenz von 1 bis n (auch Artihmetische Reihe genannt): Die Summe der kleinsten und größten Zahlen ist n, plus, 1. Weil es n Zahlen gibt, gibt es n, slash, 2 Paare (unabhängig davon ob n gerade oder ungerade ist). Daher ist die Summe der Zahlen von 1 bis n gleich left parenthesis, n, plus, 1, right parenthesis, left parenthesis, n, slash, 2, right parenthesis, was n, start superscript, 2, end superscript, slash, 2, plus, n, slash, 2. Probiere diese Formel doch mal für n, equals, 5 und n, equals, 8 aus.

Asymptotische Laufzeitanalyse von Selectionsort

Die Gesamtlaufzeit von Selectionsort besteht aus drei Teilen:
  1. Die Laufzeit für alle Anrufe von indexOfMinimum.
  2. Die Laufzeit aller Anrufe von swap.
  3. Die Laufzeit des Rests der Schleife in der selectionSort-Funktion.
Teile 2 und 3 sind einfach. Wir wissen, dass es n Anrufe von swap gibt, und jeder Anruf nimmt konstante Zeit in Anspruch. Gemäß unserer Asymptotischen Notation ist die Zeit für alle Anrufe zu swap gleich Θ(n) \Theta(n) .Der Rest der Schleife in selectionSort testet und inkrementiert lediglich die Schleifenvariable und ruft indexOfMinimum und swap auf und das dauert eine konstante Zeit für jede der n Iterationen, und damit erhalten wir ein weiteres Θ(n) \Theta(n) .
Teil 1: Die Laufzeit der Anrufe von indexOfMinimum haben wir bereits bestimmt. Jede einzelne Iteration der Schleife in indexOfMinimum dauert eine konstante Zeit. Die Anzahl der Iterationen dieser Schleife ist n im ersten Aufruf, dann n, minus, 1, dann n, minus, 2 und so weiter. Wir haben gesehen, dass diese Summe 1+2++(n1)+n 1 + 2 + \cdots + (n-1) + n eine arithmetische Reihe ist und sie left parenthesis, n, plus, 1, right parenthesis, left parenthesis, n, slash, 2, right parenthesis gleich n, start superscript, 2, end superscript, slash, 2, plus, n, slash, 2 ist. Daher ist die Gesamtzeit aller Anrufe von indexOfMinimum ein konstantes Vielfaches von n, start superscript, 2, end superscript, slash, 2, plus, n, slash, 2. In Bezug auf die Big-Θ-Notation kümmern wir uns nicht um diesen konstanten Faktor, noch kümmern wir uns um den Faktor 1/2 oder den niederwertigen Term n. Im Ergebnis ist die Laufzeit für alle Anrufe von indexOfMinimum gleich Θ(n2) \Theta (n ^ 2) .
Addieren wir nun die Laufzeiten der drei Teile, haben wir Θ(n2) \Theta (n ^ 2) für die Aufrufe von indexOfMinimum, Θ(n) \Theta (n) für die Anrufe von swap und Θ(n) \Theta (n) für den Rest der Schleife in selectionSort. Der Θ(n2) \Theta (n^2) -Term ist der bedeutendste, und so können wir aussagen, dass die Laufzeit von Selectionsort Θ(n2) \Theta (n^2) ist.
Beachte auch, dass kein Fall besonders gut oder besonders schlecht für die Selectionsort ist. Die Schleife in indexOfMinimum wird immer n, start superscript, 2, end superscript, plus, n, slash, 2 Iterationen durchführen, unabhängig von der Eingabe. Daher können wir sagen, dass Selectionsort in allen Fällen Θ(n2) \Theta (n ^ 2) Zeit benötigt.
Mal sehen, wie die Θ(n2) \Theta (n ^ 2) Laufzeit die tatsächliche Ausführungszeit beeinflusst. Angenommen, dass Selectionsort auf einem Computer ungefähr n, start superscript, 2, end superscript, slash, 10, start superscript, 6, end superscript Sekunden benötigt, um n Werte zu sortieren. Wir beginnen mit einem kleinen Wert von n, z.B. mit n, equals, 100. Dann ist die Laufzeit der Selectionsort ca. 100, start superscript, 2, end superscript, slash, 10, start superscript, 6, end superscript, equals, 1, slash, 100 Sekunden. Das scheint ziemlich schnell zu sein. Aber was ist, wenn n, equals, 1000 ist? Dann dauert Selectionsort 1000, start superscript, 2, end superscript, slash, 10, start superscript, 6, end superscript, equals, 1 Sekunde. Das Array wuchs um den Faktor 10, aber die Laufzeit wurde um das 100fache erhöht. Was ist, wenn n, equals, 1, comma, 000, comma, 000 ist? Dann dauert Selectionsort 1, comma, 000, comma, 000, start superscript, 2, end superscript, slash, 10, start superscript, 6, end superscript, equals, 1, comma, 000, comma, 000 Sekunden, was ein wenig mehr als 11,5 Tage ist. Die Erhöhung der Arraygröße um den Faktor 1000 erhöht die Laufzeit eine Million Mal!

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.