Best, Worst & Average Case
Drei Wege, um die Kosten eines Algorithmus zu messen
Die Kosten jedes Algorithmus hängen von seiner Eingabe ab. Zwei Eingaben gleicher Größe können völlig unterschiedliche Laufzeiten erzeugen. Komplexitätsanalyse formalisiert drei Perspektiven auf diese Variation.
Best Case — Ω (Omega): die Eingabe, die den Algorithmus am schnellsten beendet. Für die Linearsuche über eine Liste von N Elementen: Ω(1) — das Ziel befindet sich an der ersten Position. Ein Vergleich, fertig.
Worst Case — O (Big O): die Eingabe, die den Algorithmus am langsamsten beendet. Für die Linearsuche: O(N) — das Ziel sitzt am Ende der Liste oder fehlt ganz. Jedes Element erfordert Inspektion.
Average Case — Θ (Theta): erwartete Kosten über alle möglichen Eingaben, unter Annahme einer gleichmäßigen Verteilung. Für die Linearsuche mit dem Ziel, das mit gleicher Wahrscheinlichkeit eine beliebige der N Positionen einnehmen kann: Θ(N/2) = Θ(N). Die Konstante 1/2 fällt weg, da Theta das enge asymptotische Wachstum ausdrückt, nicht exakte Koeffizienten.
Warum Worst Case dominiert
Systeme müssen den Worst Case bewältigen. Eine Datenbankabfrage, die durchschnittlich 10 ms dauert, aber gelegentlich 60 Sekunden braucht, erzeugt einen sichtbaren Fehler für den Benutzer. Ingenieure entwerfen für Worst-Case-Grenzen, damit die Leistung unabhängig von der Eingabe vorhersehbar bleibt. Average-Case-Analyse hat Wert in probabilistischen Einstellungen, aber Worst-Case-Analyse bietet Garantien.
Fallanalyse der Binären Suche
Die binäre Suche funktioniert nur auf sortierten Arrays. Bei jedem Schritt: vergleiche das Ziel mit dem Element in der Mitte. Wenn das Ziel gleich dem mittleren Element ist, gib es zurück. Wenn das Ziel kleiner ist, rekursiv auf die linke Hälfte. Wenn größer, rekursiv auf die rechte Hälfte.
Jeder Vergleich eliminiert die Hälfte der verbleibenden Kandidaten.
Speicherwachstum & Zeit-Raum-Tradeoffs
Speicher zählen, nicht Operationen
Zeitkomplexität misst die Anzahl der Operationen, die ein Algorithmus ausführt. Raumkomplexität misst den zusätzlichen Speicher, den er über seine Eingabe hinaus zuordnet. Beide sind wichtig in Produktionssystemen: ein schneller Algorithmus, der O(N²) Speicher zuordnet, wird einen Server erschöpfen.
O(1) Speicher: konstanter zusätzlicher Speicher unabhängig von N. Ein In-Place-Sort (z.B. Insertionsort) tauscht Elemente innerhalb des ursprünglichen Arrays. Er nutzt eine Handvoll temporärer Variablen — O(1) egal wie groß das Array ist.
O(N) Speicher: Speicher proportional zur Eingabegröße. Das Erstellen einer Kopie eines N-Element-Arrays erfordert N Slots. Das Aufbauen einer Hash-Menge aus einer Liste von N Strings speichert bis zu N Einträge.
O(N²) Speicher: Speicher proportional zu N². Das Aufbauen einer N×N-Adjazenzmatrix für einen Graphen mit N Knoten erfordert N² Zellen. Bei N = 10.000 Knoten sind das 10^8 Einträge — hunderte von Megabytes für ein einfaches boolesches Gitter.
Zeit-Raum-Tradeoffs
Eines der fundamentalen Konzepte im Algorithmus-Design: Speicher für Zeit tauschen, oder Zeit für Speicher.
Hash-Tabellen nutzen O(N) zusätzlichen Speicher, um O(1) Lookup zu erreichen. Ohne die Hash-Tabelle erreicht ein Scan über eine Liste O(N) Lookup mit O(1) zusätzlichem Speicher. Die Hash-Tabelle zahlt Speicher, um Geschwindigkeit zu kaufen.
Memoization speichert zuvor berechnete Ergebnisse (O(N) oder mehr Speicher), um eine Neuberechnung zu vermeiden. Rekursives Fibonacci ohne Memoization läuft in O(2^N) Zeit. Mit Memoization: O(N) Zeit und O(N) Speicher. Die Speicherinvestition schrumpft Zeit exponentiell.
Hash-Wörterbuch vs Sortierte Liste
Vergleiche zwei Strategien zum Zählen von Wörtervorkommen in einem Dokument mit N Wörtern:
Strategie A: ein Wörterbuch (Hash-Map). Füge jedes Wort ein; erhöhe seinen Zähler.
Strategie B: verwalte eine sortierte Liste sichtbarer Wörter; nutze Binärsuche, um die Zugehörigkeit zu überprüfen, bevor du einfügst.
Amortisierte Analyse: Kosten verteilen
Wenn gelegentliche Kosten die durchschnittliche Leistung nicht ruinieren
Einige Operationen sind gelegentlich teuer, aber billig im Durchschnitt über eine Sequenz. Amortisierte Analyse berechnet die durchschnittlichen Kosten pro Operation über die gesamte Sequenz — nicht die Worst-Case-Kosten einer einzelnen Operation.
Dynamisches Array (Python list, Java ArrayList): startet mit Kapazität 1. Wenn voll, wird die Kapazität verdoppelt. Das Verdoppeln kopiert alle bestehenden Elemente: O(N) Arbeit für ein Anhängen. Aber Verdopplungen sind selten. Nach N Gesamtanhängen, wie viele Gesamtkopieroperationen traten auf?
Verdopplungen passieren bei Größen 1, 2, 4, 8, ..., N/2. Kopieranzahlen: 1 + 2 + 4 + ... + N/2. Dies ist eine geometrische Reihe, die zu N − 1 Gesamtkopien über alle N Anhänge aufsummiert. Durchschnittliche Kopien pro Anhänge: (N − 1) / N < 1, also O(1) amortisiert pro Anhänge trotz O(N) Worst-Case-Kosten pro Verdopplung.
Warum amortisierte Analyse wichtig ist
Ein System, das gelegentlich pausiert, um die Größe zu ändern, umzubalancieren oder eine Struktur zu komprimieren, kann alarmierende Worst-Case-Einzeloperationen haben. Amortisierte Analyse zeigt, dass der Alarm falsch ist: die seltenen teuren Ereignisse werden durch die vielen billigen bezahlt. Das Verständnis der amortisierten Kosten verhindert überentwicklung: das Hinzufügen von Komplexität, um eine seltene O(N) Operation zu vermeiden, die nur O(1) amortisiert beiträgt, ist verschwendete Arbeit.
Tiefer gehend: Der unhamming-Kurs wendet Komplexitätsanalyse auf reale Fehler in Produktionssoftware an. Siehe The Missing Chapter: Algorithmic Complexity & MOAD-0001: The Sedimentary Defect.
Hash-Tabellen amortisiertes Einfügen
Eine Hash-Tabelle startet leer und verdoppelt die Kapazität immer dann, wenn der Lastfaktor 0,75 überschreitet. Das Einfügen von 1.000 Elementen löst genau 10 Verdopplungen bei Kapazitäten 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 aus.