Wie schnell ist das?
Du hast dreimal gehört, ein Verfahren sei „quadratisch“. Jetzt prüfen wir das nach – auf vier verschiedene Arten. Das ist Absicht: Jede Zugangsweise zeigt etwas anderes, und keine allein reicht.
Zugang 1: Nachrechnen
Das haben wir schon getan. Sortieren durch Auswählen macht
Vergleiche. Für große n fällt der zweite Summand kaum ins Gewicht – bei n = 1000 stehen 500 000 gegen 500.
Bei Laufzeitbetrachtungen interessiert nur, wie schnell der Aufwand wächst, nicht der exakte Wert. Deshalb lässt man Vorfaktoren und kleinere Summanden weg und sagt: der Aufwand wächst wie n².
Zugang 2: Ein Bild
Zeichne ein Quadrat aus n mal n Kästchen. Die Vergleiche von Sortieren durch Auswählen sind genau die Kästchen unterhalb der Diagonalen:
j: 0 1 2 3 4
i: 0 . x x x x
i: 1 . . x x x
i: 2 . . . x x
i: 3 . . . . x
i: 4 . . . . .Zehn Kreuze bei n = 5 – genau die Zahl, die wir ausgerechnet haben. Und man sieht sofort: Es ist ungefähr die halbe Fläche des Quadrats. Wächst die Seitenlänge auf das Doppelte, wächst die Fläche auf das Vierfache.
Zugang 3: Messen
a) Führe das Programm aus und trage die Werte in eine Tabelle ein.
b) Berechne für jede Zeile den Faktor zur Zeile darüber – sowohl bei den Vergleichen als auch bei der Dauer. Was erwartest du, was misst du?
c) Führe das Programm mehrfach aus. Schwanken die Zeiten? Schwanken die Vergleiche? Erkläre den Unterschied.
Auflösung
b) Bei jeder Verdopplung von n sollte sich die Anzahl der Vergleiche vervierfachen. Das tut sie sehr genau – die Formel n·(n−1)/2 gilt exakt.
Bei den Zeiten sieht man denselben Trend, aber ungenauer. Der Faktor liegt meist zwischen 3 und 5.
c) Die Vergleiche schwanken nicht: Sortieren durch Auswählen macht immer gleich viele, unabhängig von den Daten. Die Zeiten schwanken – der Browser macht nebenher anderes, die Zwischenspeicher des Rechners sind mal besser gefüllt, mal schlechter.
Genau deshalb zählt man in der Informatik Operationen und misst nicht Sekunden. Die Messung bestätigt die Rechnung, sie ersetzt sie nicht.
Zugang 4: Die Klassen im Überblick
| Wachstum | Name | wenn n sich verdoppelt … | Beispiel |
|---|---|---|---|
| konstant | konstant | ändert sich nichts | auf feld[0] zugreifen |
| log n | logarithmisch | kommt ein Schritt dazu | Goldmünzen halbieren |
| n | linear | verdoppelt sich der Aufwand | lineare Suche |
| n² | quadratisch | vervierfacht sich der Aufwand | die drei Sortierverfahren |
| n³ | kubisch | verachtfacht sich der Aufwand | Matrizen multiplizieren |
| 2ⁿ | exponentiell | quadriert sich der Aufwand | alle Teilmengen durchprobieren |
Die Namen kennst du aus dem Matheunterricht – es sind dieselben Funktionsklassen.
Ein Verfahren braucht bei n = 1000 genau eine Sekunde. Wie lange braucht es bei n = 1 000 000?
Rechne es für jede der Klassen aus. Das Ergebnis für den exponentiellen Fall solltest du dir merken.
Auflösung
Die Anzahl wächst um den Faktor 1000.
| Klasse | Dauer bei n = 1 000 000 |
|---|---|
| logarithmisch | etwa 2 Sekunden |
| linear | etwa 17 Minuten |
| quadratisch | etwa 11,6 Tage |
| kubisch | etwa 32 000 Jahre |
| exponentiell | unvorstellbar lange – mehr als es Atome im Universum gibt |
Der Sprung von quadratisch zu kubisch ist gewaltig. Der Sprung zu exponentiell ist eine andere Kategorie: Solche Verfahren sind für große Eingaben prinzipiell unbrauchbar, egal wie schnell die Rechner werden.
Deshalb ist die Frage nach dem Aufwand keine akademische Spielerei. Sie entscheidet, ob ein Problem überhaupt lösbar ist.
Aufgabe 1: Verfahren einordnen
Ordne jedes der folgenden Verfahren einer Wachstumsklasse zu und begründe kurz.
a) Das Maximum eines Feldes bestimmen
b) Prüfen, ob ein Feld ein Duplikat enthält, indem man jedes Element mit jedem vergleicht
c) Die gefälschte Goldmünze durch Halbieren finden
d) Auf den ersten Wert eines Feldes zugreifen
e) Ein Feld mit Bubblesort sortieren, wenn es schon sortiert ist
Auflösung
a) linear – ein Durchlauf über alle Elemente.
b) quadratisch – für jedes Element ein Durchlauf über alle anderen.
c) logarithmisch – bei jeder Verdopplung der Münzzahl kommt eine Wägung dazu.
d) konstant – der Zugriff dauert immer gleich lang, egal wie groß das Feld ist.
e) linear – ein einziger Durchlauf stellt fest, dass nichts zu tun ist.
Aufgabe 2: Die drei Verfahren messen
Baue die Messung so um, dass sie alle drei Sortierverfahren auf demselben Zufallsfeld vergleicht.
Achte darauf, dass jedes Verfahren dieselben Ausgangsdaten bekommt – ein sortiertes Feld noch einmal zu sortieren, wäre kein fairer Vergleich. Du brauchst also eine Kopie.
a) Vergleiche die gemessenen Zeiten bei n = 4000.
b) Wiederhole die Messung mit einem bereits sortierten Feld. Was ändert sich, und warum?
c) Beurteile: Welches Verfahren würdest du wofür empfehlen?
Tipp: Warum braucht man überhaupt eine Kopie?
Weil ein Feld ein Objekttyp ist. Übergibst du dasselbe Feld an drei Methoden, sortiert die erste es – und die anderen beiden bekommen bereits sortierte Daten.
Das hast du in Kapitel 5 schon einmal beobachtet, als tausche das Feld des Aufrufers verändert hat.
Zusatzaufgabe
Bei den Messungen oben hast du nur einen einzigen Wert je Größe erhoben. Das ist wissenschaftlich unsauber.
a) Erweitere das Programm so, dass es jede Messung zehnmal wiederholt und den Mittelwert ausgibt.
b) Gib zusätzlich den kleinsten und den größten gemessenen Wert aus. Wie stark schwanken die Messungen?
c) Beurteile: Welche der vier Zugangsweisen aus dieser Lektion ist die verlässlichste? Begründe – und überlege, warum man trotzdem alle vier kennen sollte.