Jede Komplexitätsklasse zeichnet eine Kurve
Kosten gegen Eingabegröße darstellen
Tragen Sie die Eingabegröße N auf der x-Achse auf. Tragen Sie die Kosten (Operationen, Zeit) auf der y-Achse auf. Jede Komplexitätsklasse erzeugt eine unterschiedliche Kurve. Sie können die Wachstumsrate eines Algorithmus anhand der Form seiner Leistungskurve erkennen.
O(1) — flache horizontale Linie. Die Funktion f(N) = 1. Keine Steigung. Die Kosten ändern sich nie, unabhängig von N. Hash-Tabellen-Abfrage: Ob die Tabelle 10 oder 10.000.000 Elemente enthält, eine Hash-Berechnung springt zum richtigen Bucket.
O(log N) — sanft aufwärts gekrümmte Kurve, Steigung nimmt ab. Bei N = 1.000.000: Kosten ≈ 20 Operationen. Die Kurve steigt bei kleinen N steil an, flacht dann ab. Jede Verdopplung von N fügt genau eine Einheit Kosten hinzu.
O(N) — diagonale gerade Linie. Steigung = 1 (im asymptotischen Sinne). Die Kosten wachsen mit der gleichen Rate wie N. Wenn sich N verdreifacht, verdreifachen sich die Kosten.
O(N log N) — steilere Diagonale mit leichter aufwärts gerichteter Krümmung. Liegt über O(N), aber unter O(N²). Der Logarithmus-Faktor fügt einen langsam wachsenden Multiplikator zur linearen Steigung hinzu.
O(N²) — nach oben öffnende Parabel. Die Steigung nimmt mit wachsendem N zu. Bei N = 10: Kosten = 100. Bei N = 100: Kosten = 10.000. Bei N = 1.000: Kosten = 1.000.000.
Die wachsende Lücke
Das Verhältnis O(N²) / O(N) = N. Die Lücke zwischen der Parabel und der Diagonale wird größer, wenn N wächst. Bei N = 10: 10× Lücke. Bei N = 100: 100× Lücke. Bei N = 1.000: 1.000× Lücke. Bei N = 50.000: 50.000× Lücke. Die Lücke ist gleich N — immer.
Berechnung der Skalenlücke
Ein großer Abhängigkeitsgraph enthält 50.000 Pakete (N = 50.000). Ein Algorithmus läuft in O(N)-Zeit. Ein zweiter läuft in O(N²)-Zeit. Bei diesem N ist das Verhältnis O(N²)/O(N) = N = 50.000.
Halbieren eines Liniensegments
Binäre Suche als wiederholte Halbierung
Ein sortiertes Array mit N Elementen bildet ein Liniensegment der Länge N. Die binäre Suche halbiert dieses Segment wiederholt:
1. Zeigen Sie auf den Mittelpunkt des verbleibenden Segments.
2. Wenn Ziel < Mittelpunkt: Die rechte Hälfte verschwindet. Rekursieren Sie auf der linken Hälfte.
3. Wenn Ziel > Mittelpunkt: Die linke Hälfte verschwindet. Rekursieren Sie auf der rechten Hälfte.
4. Wenn Ziel = Mittelpunkt: fertig.
Nach k Halbierungen hat das verbleibende Segment die Länge N / 2^k. Die Suche endet, wenn diese Länge gleich 1 ist:
N / 2^k = 1 → 2^k = N → k = log₂N
Die binäre Suche auf N Elementen erfordert also höchstens log₂N Vergleiche.
Halbierung & Verdopplung: Zwei Seiten der gleichen Kurve
Halbierung und Verdopplung sind geometrische Umkehrungen. Die Exponentialkurve 2^k und die logarithmische Kurve log₂N sind Spiegelungen voneinander über der Linie y = x.
Betrachten Sie das Falten von Papier: Ein Blatt beginnt mit einer Dicke von 0,1 mm. Jede Falte verdoppelt die Dicke. Nach 42 Falten: 0,1 mm × 2^42 ≈ 439.804 km — vorbei am Mond (384.400 km). Die binäre Suche läuft umgekehrt: Beginnen Sie mit N Elementen, jeder Schritt halbiert die Anzahl, erreichen Sie 1 Element in log₂N Schritten.
Die Geometrie: Halbierung ist eine selbstähnliche Operation. Jede Halbierung erzeugt zwei Hälften, die strukturell identisch mit dem Ganzen aussehen. Rekursion und Logarithmen teilen diese Selbstähnlichkeit.
Vergleiche & Verdopplung
Ein sortiertes Array enthält 1.048.576 Elemente. Hinweis: 1.048.576 = 2^20.
Eine Hash-Funktion als geometrische Abbildung
Hash-Funktion als Funktion
Eine Hash-Tabelle ordnet einen Schlüssel mithilfe einer Hash-Funktion einem Bucket zu:
bucket = hash(key) mod table_size
Dies ist eine Funktion im strengen mathematischen Sinne: Sie ordnet einen Definitionsbereich (alle möglichen Schlüssel) einem Wertebereich (Bucket-Indizes 0 bis table_size − 1) zu. Das geometrische Bild: Schlüssel nehmen einen Platz ein; Buckets nehmen einen anderen ein. Die Hash-Funktion projiziert Schlüssel auf Bucket-Indizes.
O(1)-Abfrage — direkter Sprung, keine Suche. Die Hash-Funktion berechnet den Bucket-Index in konstanter Zeit. Springen Sie direkt zu diesem Bucket. Keine Traversierung, keine Vergleichsschleife.
Auslastungsfaktor. Bei einem Auslastungsfaktor von 0,75 enthalten 75% der Buckets mindestens ein Element. Über ~0,9 nehmen Kollisionen zu: Zwei Schlüssel führen zu demselben Bucket und bilden eine Kette von Elementen in diesem Bucket. Die Abfrage in einer langen Kette verschlechtert sich im ungünstigsten Fall auf O(N).
Verteilungsqualität als Geometrie
Eine gut verteilte Hash-Funktion verteilt Schlüssel gleichmäßig über alle Buckets. Geometrisch: Der Wertebereich der Funktion deckt ihre Codomäne gleichmäßig ab. Jeder Bucket erhält ungefähr N / table_size Schlüssel.
Eine schlecht verteilte Hash-Funktion clustert Schlüssel in wenigen Buckets. Geometrisch: Der Wertebereich der Funktion kollabiert zu einer Teilmenge der Codomäne — die meisten Schlüssel werden auf die gleichen wenigen Punkte abgebildet. Die verbleibenden Buckets sitzen leer.
Verbindung zu MOAD-0001
Das Ersetzen einer Liste durch eine Menge behebt MOAD-0001, da eine Menge intern eine Hash-Tabelle verwendet. O(N)-Listenüberprüfung → O(1)-Hash-Tabellen-Abfrage. Geometrisch: Eine lineare Traversierung entlang einer Sequenz transformiert sich in eine direkte Projektion über eine Funktion. Die Sequenz verschwindet; die Funktion ersetzt sie.
Analyse einer schlecht verteilten Hash-Funktion
Eine Hash-Tabelle hat 1.000 Buckets und 900 Elemente (Auslastungsfaktor 0,9). Eine schlecht verteilte Hash-Funktion sendet 500 dieser Elemente zum selben Bucket.