Jede Komplexitätsklasse zeichnet eine Kurve
Kosten gegen Eingabegröße plotten
Setzen Sie die Eingabegröße N auf die x-Achse. Setzen Sie die Kosten (Operationen, Zeit) auf die y-Achse. Jede Komplexitätsklasse erzeugt eine eindeutige Kurve. Sie können die Wachstumsrate eines Algorithmus von der Form seiner Leistungskurve erkennen.
O(1) — flache horizontale Linie. Die Funktion f(N) = 1. Keine Neigung. Die Kosten ändern sich nie, unabhängig von N. Hash-Tabellenauswahl: Ob das Tableau 10 oder 10.000.000 Elemente enthält, springt eine Hash-Berechnung direkt zum richtigen Bucket.
O(log N) — sanft ansteigende Kurve, abnehmende Neigung. Bei N = 1.000.000: Kosten ≈ 20 Operationen. Die Kurve steigt steil bei kleinem N, dann flacht ab. Jede Verdoppelung von N fügt genau einen Kosten-Einheit hinzu.
O(N) — diagonale geradlinige Linie. Neigung = 1 (im asymptotischen Sinne). Kosten wachsen im gleichen Tempo wie N. Wenn N sich dreifacht, treiben sich die Kosten ebenfalls dreifacht.
O(N log N) — steilere Diagonale mit leichter aufwärts gerichteter Krümmung. Liegt über O(N) und unter O(N²). Der Log-Faktor fügt einem linearen Anstieg einen langsam wachsenden Multiplikator hinzu.
O(N²) — nach oben geöffnete Parabel. Neigung erhöht sich, wenn N wächst. Bei N = 10: Kosten = 100. Bei N = 100: Kosten = 10.000. Bei N = 1.000: Kosten = 1.000.000.
Die wachsende Kluft
Das Verhältnis O(N²) / O(N) = N. Die Kluft zwischen Parabel und Diagonale wird mit wachsendem N immer größer. Bei N = 10: 10-fache Kluft. Bei N = 100: 100-fache Kluft. Bei N = 1.000: 1.000-fache Kluft. Bei N = 50.000: 50.000-fache Kluft. Die Kluft entspricht N — immer.
Berechnung des Skalierungsabstands
Ein großes Abhängigkeitsdiagramm 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 beträgt das Verhältnis O(N²)/O(N) = N = 50.000.
Teilung eines Streckenabschnitts
Binärsuchalgorithmus als wiederholte Teilung
Ein sortierter Array von N Elementen bildet einen Streckenabschnitt der Länge N ab. Der Binärsuchalgorithmus teilt diesen Abschnitt wiederholt auf:
1. Zeigen Sie auf die Mittelpunkt des verbleibenden Abschnitts.
2. Wenn Ziel < Mittelpunkt: der rechte Halbierung verschwindet. Rekursiv auf dem linken Halbierung.
3. Wenn Ziel > Mittelpunkt: der linke Halbierung verschwindet. Rekursiv auf dem rechten Halbierung.
4. Wenn Ziel = Mittelpunkt: fertig.
Nach k Teilungen hat der verbleibende Abschnitt die Länge N / 2^k. Die Suche endet, wenn diese Länge 1 beträgt:
N / 2^k = 1 → 2^k = N → k = log₂N
So benötigt der Binärsuchalgorithmus für N Elemente maximal log₂N Vergleiche.
Halbierung & Verdopplung: Zwei Seiten derselben Kurve
Halbierung und Verdopplung sind geometrische Inversen. Die exponentielle Kurve 2^k und die logarithmische Kurve log₂N sind Spiegelbilder derenander über der Geraden y = x.
Überlegung: Papierfalten: ein Blatt beginnt mit einer Dicke von 0,1 mm. Jede Faltung verdoppelt die Dicke. Nach 42 Faltungen: 0,1 mm × 2^42 ≈ 439.804 km — jenseits des Mondes (384.400 km). Der Binärsuchalgorithmus führt die Umkehrung durch: Starten Sie mit N Elementen, jedes Schritt halbiert die Anzahl, erreichen Sie ein Element in log₂N Schritten.
Die Geometrie: Teilung ist eine selbstähnliche Operation. Jede Teilung erzeugt zwei Hälften, die in der Struktur identisch zum Ganzen aussehen. Rekursion und Logarithmen teilen diese Selbstähnlichkeit.
Vergleiche & Verdopplungen
Ein sortiertes Array enthält 1.048.576 Elemente. Tipp: 1.048.576 = 2^20.
Ein Hash-Funktion als geometrische Karte
Hash-Funktion als Funktion
Eine Hash-Tabelle verbindet eine Schlüssel mit einem Bucket mit einer Hash-Funktion:
bucket = hash(key) mod table_size
Dies ist eine Funktion im strengen mathematischen Sinne: Sie abbildet einen Bereich (alle möglichen Schlüssel) auf einen Bereich (Taschenindizes von 0 bis table_size − 1). Das geometrische Bild: Schlüssel nehmen einen Raum ein; Taschen nehmen einen anderen. Die Hash-Funktion projiziert Schlüssel auf Taschenindizes.
O(1) Suche - direkter Sprung, keine Suche. Die Hash-Funktion berechnet den Taschenindex in konstanter Zeit. Springen Sie direkt zu diesem Bucket. Keine Durchführung, keine Vergleichschleife.
Ladefaktor. Bei einem Ladefaktor von 0,75 befinden sich 75% der Taschen mindestens einen Element enthalten. Über ~0,9 erhöhen sich Kollisionen: Zwei Schlüssel hash in den gleichen Bucket, bilden eine Kette von Elementen innerhalb dieses Buckets. Die Suche in einer langen Kette degradiert im schlimmsten Fall zu O(N).
Qualität der Verteilung als Geometrie
Eine gut verteilt Hash-Funktion verteilt Schlüssel gleichmäßig auf alle Buckets. Geometrisch: Die Funktion deckt ihren Kodomain gleichmäßig ab. Jeder Bucket erhält ungefähr N / table_size Schlüssel.
Eine schlecht Hash-Funktion klumpt Schlüssel in wenigen Buckets. Geometrisch: Die Funktion range zusammenfaltet auf einen Teil des Codomains - die meisten Schlüssel mappen auf die gleichen wenigen Punkte. Die verbleibenden Buckets sind leer.
Verbindung zu MOAD-0001
Das Ersetzen einer Liste durch ein Satz behebt MOAD-0001, weil ein Satz eine Hash-Tabelle intern verwendet. O(N) Liste Scan → O(1) Hash-Tabelle Suche. Geometrisch: Lineare Durchführung entlang einer Sequenz verwandelt sich in einen direkten Projektion via einer Funktion. Die Sequenz verschwindet; die Funktion ersetzt sie.
Analyse einer schlecht verteilt Hash
Eine Hash-Tabelle hat 1.000 Beutel und 900 Elemente (Ladequote 0,9). Ein schlechter Hash-Funktion sendet 500 dieser Elemente in den gleichen Beutel.