If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

Kurs: Informatik > Lerneinheit 1

Lektion 4: Auswahl sortieren
Informatik
Informatik
Algorithmen
Auswahl sortieren
© 2024 Khan AcademyNutzungsbedingungenDatenschutzerklärungCookie-Meldung

Analyse von Selectionsort

Google Classroom
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 2n Zeilen Code durch Selectionsort ausgeführt werden. Aber es ist nicht richtig, denn indexOfMinimum und swap 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. …
  6. 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=4⋅9=36 .
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,5⋅6=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+1. Weil es n Zahlen gibt, gibt es n/2 Paare (unabhängig davon ob n gerade oder ungerade ist). Daher ist die Summe der Zahlen von 1 bis n gleich (n+1)(n/2), was n2/2+n/2. Probiere diese Formel doch mal für n=5 und n=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).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).
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−1, dann n−2 und so weiter. Wir haben gesehen, dass diese Summe 1+2+⋯+(n−1)+n eine arithmetische Reihe ist und sie (n+1)(n/2) gleich n2/2+n/2 ist. Daher ist die Gesamtzeit aller Anrufe von indexOfMinimum ein konstantes Vielfaches von n2/2+n/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).
Addieren wir nun die Laufzeiten der drei Teile, haben wir Θ(n2) für die Aufrufe von indexOfMinimum, Θ(n) für die Anrufe von swap und Θ(n) für den Rest der Schleife in selectionSort. Der Θ(n2)-Term ist der bedeutendste, und so können wir aussagen, dass die Laufzeit von Selectionsort Θ(n2) ist.
Beachte auch, dass kein Fall besonders gut oder besonders schlecht für die Selectionsort ist. Die Schleife in indexOfMinimum wird immer n2/2+n/2 Iterationen durchführen, unabhängig von der Eingabe. Daher können wir sagen, dass Selectionsort in allen Fällen Θ(n2) Zeit benötigt.
Mal sehen, wie die Θ(n2) Laufzeit die tatsächliche Ausführungszeit beeinflusst. Angenommen, dass Selectionsort auf einem Computer ungefähr n2/106 Sekunden benötigt, um n Werte zu sortieren. Wir beginnen mit einem kleinen Wert von n, z.B. mit n=100. Dann ist die Laufzeit der Selectionsort ca. 1002/106=1/100 Sekunden. Das scheint ziemlich schnell zu sein. Aber was ist, wenn n=1000 ist? Dann dauert Selectionsort 10002/106=1 Sekunde. Das Array wuchs um den Faktor 10, aber die Laufzeit wurde um das 100fache erhöht. Was ist, wenn n=1,000,000 ist? Dann dauert Selectionsort 1,000,0002/106=1,000,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.

Willst du an der Diskussion teilnehmen?

Anmelden
Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.