Bisher haben wir die Laufzeit der verwendeten Sortierverfahren experimentell untersucht und einige informelle Beobachtungen angestellt, wie sich die Laufzeit für unterschiedliche Eingaben in Abhängigkeit der Eingabegröße verhält. Im Folgenden kategorisieren wir unsere Beobachtungen und lernen eine Notation kennen, um die Laufzeit von Algorithmen abstrakt zu beschreiben.
Bei Insertion Sort haben wir beobachtet, dass die Laufzeit davon abhängt, ob Elemente bereits vorsortiert sind oder nicht. Bei bereits sortierten Listen verdoppelte sich die Laufzeit bei Verdoppelung der Eingabegröße, bei unsortierten Listen vervierfachte sie sich hingegen.
Tatsächlich ist Insertion Sort bei bereits sortierten Listen am schnellsten und bei umgekehrt sortierten Listen am langsamsten. Es ist deshalb hilfreich, die sogenannte Best-Case- von der Worst-Case-Komplexität zu unterscheiden.
Statt konkreter Laufzeiten gibt man in der Regel eine Funktion an, die das Wachstum der Laufzeit in Abhängigkeit von der Eingabegröße angibt. Im Worst Case für Insertion Sort hat sich die Laufzeit bei Verdopplung vervierfacht, bei Vervierfachung also versechzehnfacht und so weiter. Dies entspricht der Quadratfunktion. Man sagt deshalb: “Die Worst-Case-Komplexität von Insertion Sort ist quadratisch in Abhängigkeit der Größe der sortierten Liste.”
Alternativ sagt man auch: “Die Worst-Case-Komplexität von Insertion Sort ist in \(\mathcal{O}(n^2)\), wobei \(n\) die Größe der sortierten Liste ist.” Die hier verwendete \(\mathcal{O}\) -Notation hat eine genau definierte mathematische Bedeutung, die uns hier aber nicht weiter beschäftigen soll. Sie formalisiert die oben intuitiv beschriebene Angabe der Laufzeit als Funktion der Eingabegröße, hier \(n\) genannt. Dabei haben Algorithmen der Komplexität \(\mathcal{O}(1) = \mathcal{O}(42) = \mathcal{O}(4711)\) die gleiche abstrahierte Laufzeit. Man spricht hier auch von konstanter Laufzeit, weil diese nicht von der Eingabegröße abhängt. Außerdem gilt zum Beispiel \(\mathcal{O}(n^2) = \mathcal{O}(\frac{n^2−n}{2})\) . Die \(\mathcal{O}\)-Notation abstrahiert die Laufzeit also so, dass von Polynomfunktionen nur der Anteil mit dem größten Exponenten von Bedeutung ist. Intuitiv wird dadurch kenntlich gemacht, wie sich die Laufzeit für sehr große Eingaben verhält. Je größer das \(n\), desto weniger fallen die Anteile mit kleinerem Exponenten ins Gewicht. Auch konstante Faktoren (wie \(\frac{1}{2}\) im obigen Beispiel) werden vernachlässigt.
Die folgende Tabelle fasst die Best- und Worst-Case-Laufzeiten der definierten Sortierverfahren zusammen.
| Algorithmus | Best Case (sortiert) | Worst Case (unsortiert) |
|---|---|---|
| Selection Sort | \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n^2)\) |
| Insertion Sort | \(\mathcal{O}(n)\) | \(\mathcal{O}(n^2)\) |
Selection Sort hat im Best und im Worst Case die gleiche Komplexität, während Insertion Sort im Best Case besser ist als im Worst Case.
Statt die Komplexitäten experimentell zu ermitteln, können wir sie auch anhand des Programms ermitteln.
Selection Sort verwendet im Wesentlichen zwei geschachtelte Wiederholungen. Die äußere durchläuft einmal die gegebene Liste, wobei in jedem Schritt die innere Wiederholung vom aktuellen Element bis zum Ende läuft, um das kleinste Elemente in diesem Bereich zu finden. Wenn \(n\) die Eingabegröße ist, werden (für \(n > 1\)) insgesamt \((n − 1) + \dots + 1 = \sum\limits_{i=1}^{n-1} i = \frac{(n-1)n}{2} = \frac{n^2-n}{2}\) Vergleiche ausgeführt. Für die Worst-Case-Komplexität von Insertion Sort ergibt sich auf ähnliche Weise dieselbe Anzahl von Vergleichen. Im Best Case wird die innere Schleife von Insertion Sort nicht ausgeführt. In diesem Fall ergeben sich also \(n − 1\) Vergleiche.
Neben Best- und Worst-Case-Komplexität betrachtet man manchmal auch noch Average-Case-Komplexität, also die durchschnittliche Laufzeit gemittelt über alle möglichen Eingaben. Wir werden im nächsten Abschnitt ein Sortierverfahren kennen lernen, dessen Average-Case-Komplexität sich von der Worst-Case-Komplexität unterscheidet.