Zeitkomplexität und Speicherkomplexität eines Algorithmus erklärt
Stellen Sie sich zwei Programme vor, die exakt dieselbe Aufgabe erfüllen. Geben Sie jedem tausend Datensätze, und Sie können sie nicht unterscheiden. Geben Sie ihnen jedoch eine Milliarde Datensätze, und das eine ist fertig, bevor Sie die Eingabetaste losgelassen haben, während das andere noch am nächsten Dienstag weiterarbeitet.
Derselbe Laptop. Dieselben Daten. Der Unterschied liegt in der Zeitkomplexität, die lediglich angibt, wie schnell die Arbeitslast eines Algorithmus ansteigt, wenn man ihm mehr Eingaben gibt.
Wir werden uns ansehen, was der Begriff genau bedeutet, wie die Big-O-Notation ihn darstellt, wie man ihn anhand eines realen Codebeispiels ermittelt und wo die Speicherkomplexität ins Spiel kommt. Und schließlich, ganz am Ende, kommen wir zu einem Punkt, an dem das Ganze nicht mehr nur Hausaufgaben sind, sondern tatsächlich Geld kostet: Smart Contracts.
Was ist die Zeitkomplexität eines Algorithmus?
Vergessen Sie für einen Moment die Sekunden. Die Zeitkomplexität zählt die Schritte. Vergleiche, Zuweisungen, ein bisschen Arithmetik hier und da, und man schreibt die Gesamtsumme als Funktion von n, der Eingabegröße.
Hier kommt die wohl langweiligste Funktion, die man sich vorstellen kann:
python def print_all(items): for item in items: print(item)
Zehn Gegenstände? Zehn Durchläufe. Zehntausend? Zehntausend Durchläufe.
Der Rechenaufwand steigt linear mit dem Input an, daher nennen wir ihn O(n).
Nun, vielleicht erfordert jede Reise in Wirklichkeit drei kleine Arbeitsschritte statt nur einem. Gut, dann sind es 3n. Ehrlich gesagt, ist das egal, denn die Verdopplung der Liste bedeutet immer noch die Verdopplung der Arbeit, und genau diese Wachstumskurve ist es, die wir brauchen. Die genaue Zahl wird absichtlich weggelassen.
Deshalb wird in jedem DSA-Kurs und in der Hälfte aller Programmier-Interviews die Zeitkomplexität so stark betont. Wenn man die Komplexität eines Algorithmus ablesen kann, lässt sich sein Verhalten bei Eingabedaten, die man nie getestet hat, erahnen. Und genau das betrifft in der Praxis den Großteil der Daten.
Warum die Ausführungszeit ein schlechtes Maß für einen Algorithmus ist
Warum also nicht einfach mit einem Timer laufen lassen? Viele machen das, und ich verstehe das. Der Haken ist, dass die Ausführungszeit eine Menge Zeug mit sich bringt, mit dem dein Algorithmus nichts zu tun hat:
- Hardware. Mein fünf Jahre alter Laptop und eine brandneue Cloud-Box liefern für dasselbe Skript völlig unterschiedliche Ergebnisse.
- Programmiersprache. Schreiben Sie dieselbe Schleife in C und in Python, und Sie werden möglicherweise einen Unterschied von 10-facher oder mehr feststellen.
- Systemlast. Ein Hintergrundprozess wird aktiv, die Speicherbereinigung wird aktiviert, der Cache ist leer. Ihr Ergebnis verschiebt sich.
- Ganz gleich, welche Eingabedaten Sie gerade erfasst haben. Ein Sortieralgorithmus, der bei fast sortierten Daten blitzschnell arbeitet, kann bei gemischten Daten extrem langsam sein.
Eine Stoppuhr liefert Ihnen einen Durchlauf an einem Gerät mit einer Eingabe. Fragen Sie sie nach der 100-fachen Datenmenge, und sie liefert keine Ergebnisse.
Die Anzahl der Schritte variiert nicht. Derselbe Algorithmus, dieselbe Eingabe, und man erhält dieselbe Anzahl an Schritten, egal ob Rust auf einem Rack-Server oder JavaScript auf einem Smartphone ausgeführt wird. Deshalb ist die Zeitkomplexität ein fairer Vergleich zweier Lösungen, noch bevor man Benchmarks durchgeführt hat. Ich würde trotzdem im Nachhinein Benchmarks durchführen, nur so nebenbei. Es ist einfach eine andere Fragestellung.
Erklärung der Big-O-Notation und anderer asymptotischer Notationen
In Lehrbüchern wird dies als asymptotische Notation bezeichnet, was komplizierter klingt, als es ist. Man lässt n enorm groß werden und vernachlässigt die Details, sodass konstante Multiplikatoren und winzige Inputfaktoren wegfallen und nur die Wachstumskurve übrig bleibt. Drei davon sind besonders wichtig:
| Notation | Was es beschreibt | Einfache Bedeutung | Beispiel |
|---|---|---|---|
| Big O, O(f(n)) | Obergrenze | Der Algorithmus wächst nicht schneller als f(n). | Die lineare Suche hat die Komplexität O(n). |
| Big-Omega, Ω(f(n)) | Untere Grenze | Der Algorithmus benötigt mindestens f(n) Arbeit. | Jeder Vergleichssortieralgorithmus ist Ω(n log n) |
| Big-Theta, Θ(f(n)) | Fest gebunden | Ober- und Untergrenze stimmen überein | Mergesort ist Θ(n log n) |
In der Praxis hört man die Big-O-Notation in etwa 95 % der Fälle. Sie legt eine obere Schranke fest, was bedeutet, dass die Laufzeit nicht schneller wächst als der Wert in den Klammern. Bei meiner ersten Code-Review im Job schrieb ein Senior-Entwickler neben eine verschachtelte Schleife „O(n²), bitte beheben“. Damit meinte er, dass die Laufzeitkomplexität im schlimmsten Fall quadratisch war und die Liste bald deutlich länger werden würde.
Omega und Theta findet man hauptsächlich in Universitätskursen zur Algorithmenanalyse, und ich glaube, ich habe beide seit Jahren nicht mehr im Berufsleben verwendet. Die O-Notation ist die bessere Wahl, weil sie die Frage beantwortet, die in Meetings tatsächlich gestellt wird: „Wie schlimm wird es, wenn sich der Datenverkehr verdreifacht?“
Eine technische Feinheit hat mich eine Weile verwirrt. Da die O-Notation nur eine obere Schranke ist, ist eine Funktion der Komplexität O(n) streng genommen auch O(n²), genauso wie eine 1,52 m große Person „unter 2,13 m“ ist. Stimmt zwar, ist aber nutzlos. Jeder gibt die engste Schranke an, die er begründen kann, und ich tue es ihm gleich.
Gängige Zeitkomplexitätsklassen mit Beispielen
Es gibt nicht viele Klassen, die man im realen Code sieht, vielleicht sieben, wenn man die schwierigen mitzählt. Das sind ungefähr die Kosten jeder Klasse bei n = 1.000:
| Klasse | Name | Typisches Beispiel | Operationen bei n = 1.000 |
|---|---|---|---|
| O(1) | Konstante | Array-Index, Hashtabellen-Lookup | 1 |
| O(log n) | Logarithmisch | Binärsuche | ~10 |
| An) | Linear | Scannen einer Liste | 1.000 |
| O(n log n) | Linearithmisch | Mergesort, Quicksort (Durchschnitt) | ~10.000 |
| O(n²) | Quadratisch | Verschachtelte Schleifen, Bubblesort | 1.000.000 |
| O(2ⁿ) | Exponentiell | Naive rekursive Fibonacci-Folge | Mehr als Atome im Universum |
| An!) | Fakultät | Brutaler Handelsreisender | Noch größer |
O(1): Konstante Zeit
Ob Ihr Python-Dictionary zehn oder zehn Millionen Schlüssel hat, das Abrufen eines Elements anhand seines Schlüssels ist in etwa gleich zeitaufwendig, genauso wie das Lesen von `items[5]` aus einer Liste. Diese flache Struktur ist der Kern der konstanten Laufzeit.
O(log n): Logarithmische Zeit
Ich betrachte diese Algorithmen als „Zahlen zwischen 1 und 100 erraten“, wobei jeder Versuch die Hälfte der verbleibenden Möglichkeiten ausschließt. Die binäre Suche macht genau das auf einer sortierten Liste:
python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
Bei einer Milliarde sortierter Elemente sind etwa 30 Vergleiche nötig, während das mühsame Durchgehen jedes einzelnen Elements die gesamte Milliarde in Anspruch nehmen könnte, und ich finde das immer noch ziemlich witzig.
O(n) und O(n log n)
Ein linearer Algorithmus durchläuft jedes Element eine festgelegte Anzahl von Malen, ähnlich wie beim manuellen Suchen nach dem größten Wert in einer Tabellenspalte. O(n log n) ist die Grundlage für gute Sortieralgorithmen. Mergesort zerlegt die Liste in einzelne Elemente (log n Aufteilungsebenen) und führt dann pro Ebene einen linearen Durchlauf durch, während die Elemente zusammengeführt werden. Die Laufzeit bleibt daher konstant, unabhängig davon, ob die Daten sortiert oder durcheinander vorliegen.
O(n²) und schlechter
Quadratischer Code enthält fast immer eine in einer anderen Schleife verschachtelte Schleife, wie beispielsweise diese Duplikatsprüfung, die jedes Paar vergleicht:
python def has_duplicate(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False
Exponentielles und faktorielles Wachstum sind um ein Vielfaches schlimmer. Die rekursive Fibonacci-Folge aus Lehrbüchern löst immer wieder dieselben Teilprobleme, sodass jede Erhöhung von n um 1 den Arbeitsaufwand annähernd verdoppelt. Bei n = 20 merkt man das noch nicht; bei n = 60 kann man kochen, essen und abwaschen, und die Aufgabe ist immer noch nicht erledigt.
Wie man die Zeitkomplexität Schritt für Schritt berechnet
Man benötigt fast nie einen formalen Beweis, um die Zeitkomplexität zu berechnen. Ich gehe diese Liste im Kopf durch, und sie deckt den Großteil des Codes ab, den ich sehe:
- Definiere n. Lege fest, was die Eingabegröße ist: die Länge einer Liste, die Anzahl der Knoten in einem Graphen, die Anzahl der Ziffern in einer Zahl.
- Zählen Sie die Arbeit in jeder Zeile. Einfache Anweisungen (Zuweisungen, Vergleiche, Arithmetik) haben einen Aufwand von O(1).
- Füge sequentielle Blöcke hinzu. Zwei Schleifen nacheinander, jede über n, ergeben n + n = 2n.
- Multipliziere verschachtelte Blöcke. Eine Schleife über n innerhalb einer anderen Schleife über n ergibt n × n = n².
- Konstanten werden weggelassen. 2n wird zu n und 500 zu 1.
- Behalte nur den dominanten Term bei. In n² + n wird der n²-Term mit wachsendem n immer kleiner.
Eine kurze Berechnung ergibt T(n) = 3n² + 5n + 2. Setzen wir eine Million ein: 3n² sind drei Billionen, 5n sind fünf Millionen. Rundungsfehler. Nennen wir es O(n²), fertig.
Schleifen, die anstatt Schritte um eins zu machen, um eins herumgehen, sind heimtückischer:
python def count_halvings(n): steps = 0 while n > 1: n //= 2 steps += 1 return steps
Bei jedem Durchlauf wird n halbiert, daher gibt die while-Schleife nach etwa log₂(n) Durchläufen auf. Das ist im Grunde die Antwort auf die Frage: „Wann ist die Zeitkomplexität O(log n)?“ Wenn sich der verbleibende Wert in jedem Schritt um einen konstanten Faktor verringert, ist das Ziel erreicht.
Rekursion benötigt ein weiteres Werkzeug, eine Rekursionsgleichung. Mergesort führt zwei halb so große Sortiervorgänge durch und führt anschließend eine Zusammenführung durch, sodass T(n) = 2T(n/2) + n. Der Mastersatz dient als Spickzettel für Rekursionsgleichungen dieser Form und liefert in diesem Fall O(n log n).
Eine Faustregel aus dem Wettbewerbsprogrammieren, auf die ich mich oft stütze: Ein normaler Rechner schafft etwa 10⁸ einfache Operationen pro Sekunde. Sehr grob geschätzt, aber ausreichend, um die Zeitkomplexität einer Lösung vor dem Absenden zu überprüfen. Bei n = 10⁵ entspricht O(n²) etwa 10¹⁰ Operationen, also tritt ein Timeout auf. O(n log n) liegt unter 2 Millionen. Läuft problemlos.
Worst-Case-, Best-Case- und Durchschnittsfallanalyse
Gibt man demselben Algorithmus unterschiedliche Eingaben, kann der Arbeitsaufwand stark schwanken. Die lineare Suche veranschaulicht dies gut:
- Im besten Fall sitzt das, was du willst, ganz vorne. Ein Vergleich, und du bist raus.
- Im schlimmsten Fall: Es befindet sich ganz am Ende oder ist gar nicht vorhanden. Das sind n Vergleiche.
- Im Normalfall: Wenn es überall mit gleicher Wahrscheinlichkeit sein könnte, überprüft man im Durchschnitt etwa n/2. Wohlgemerkt, es bleibt O(n).
Fragt man einen Entwickler nach der „Komplexität“ einer Sache, wird er einem fast immer die Worst-Case-Zeitkomplexität nennen, denn diese Zahl ist ein Versprechen, mit dem man planen kann.
Angenommen, Ihre API verarbeitet eine Anfrage im schlimmsten Fall in O(n). Perfekt, jetzt wissen Sie, wie sich die langsamste Anfrage verhält, und sind auch abgesichert, falls Ihnen jemand absichtlich fehlerhafte Daten sendet. Das kommt durchaus vor: Wenn ein Angreifer herausfindet, welche Schlüssel zu einer Kollision Ihrer Hashtabelle führen, werden Sie für eine Weile nur noch diese Schlüssel sehen.
Der Durchschnittsfall ist interessant, da ungünstige Szenarien äußerst selten auftreten. Quicksort ist hierfür ein Paradebeispiel: Die durchschnittliche Laufzeit beträgt O(n log n), kann aber auf O(n²) ansteigen, wenn man Pivotelemente naiv auf bereits sortierten Daten auswählt. Standardbibliotheken umgehen dieses Problem mit zufälligen Pivotelementen oder indem sie bei verdächtig tiefen Rekursionen auf einen anderen Sortieralgorithmus umsteigen.
Was versteht man unter Speicherkomplexität und Hilfsspeicher?
Der Speicherbedarf ist der andere Kostenfaktor eines Algorithmus. Die Speicherkomplexität gibt an, wie viel Speicher mit zunehmender Eingabegröße benötigt wird, und wird mit der gleichen Big-O-Notation wie die Zeit ausgedrückt.
Ein Teil dieses Speichers besteht aus den Eingabedaten selbst, für die Sie bezahlen müssen, egal was Sie damit machen. Der Teil, den Sie tatsächlich kontrollieren können, wird als Hilfsspeicher bezeichnet. Das bedeutet den zusätzlichen Speicher, den Ihr Code während der Ausführung belegt, wie temporäre Variablen und neue Arrays, sowie den Aufrufstapel, an den sich niemand erinnert, bis es zu Problemen kommt.
Einige kurze Beispiele:
- Das Vertauschen zweier Variablen benötigt unabhängig von allem anderen ein paar Speicherplätze, daher ist der zusätzliche Speicherplatz O(1).
- Das Kopieren einer Liste mit n Elementen in eine neue Liste kostet O(n) zusätzlichen Speicherplatz.
- Wenn man rekursiv n Ebenen tief ruft, bleiben n Frames auf dem Stack liegen, was O(n) Speicherplatz benötigt, obwohl man nie ein Array erstellt hat.
Ich habe miterlebt, wie ein junger Entwickler deswegen einen ganzen Nachmittag verloren hat. Seine rekursive Funktion schien überhaupt keinen Speicher zu verbrauchen, aber jeder unfertige Aufruf wurde auf dem Stack geparkt und wartete darauf, dass die tieferen Aufrufe zurückkehrten, und bei einer großen Eingabe stürzte das Ganze mit einem Stack-Überlauf ab.
Viele Optimierungen basieren auf dem Tausch von Speicherplatz gegen Rechenzeit oder umgekehrt. Memoization speichert bereits berechnete Ergebnisse im Cache, wodurch die Laufzeit einer einfachen Fibonacci-Folge von O(2ⁿ) auf O(n) reduziert wird, bei gleichzeitigem Bedarf an O(n) Speicherplatz. Hashtabellen ermöglichen durchschnittliche Suchvorgänge in O(1), indem Speicherplatz für Buckets genutzt wird. Auf einem Server mit 64 GB RAM ist dieser Tausch meist unproblematisch, auf einem Mikrocontroller oder in einem Smart Contract sollte man ihn jedoch gut überdenken.
Zeit- und Speicherkomplexität gängiger Datenstrukturen
Die Wahl der richtigen Datenstruktur ist in der Regel wichtiger als die Feinabstimmung des Codes innerhalb der Schleife. Durchschnittliche Kosten für die am häufigsten verwendeten Datenstrukturen:
| Datenstruktur | Zugang | Suchen | Einfügen | Löschen | Raum |
|---|---|---|---|---|---|
| Array | O(1) | An) | An) | An) | An) |
| Verkettete Liste | An) | An) | O(1) | O(1) | An) |
| Hashtabelle | n / A | O(1) | O(1) | O(1) | An) |
| Ausgeglichener binärer Suchbaum | O(log n) | O(log n) | O(log n) | O(log n) | An) |
| Binärer Heap | O(1) für min/max | An) | O(log n) | O(log n) | An) |
Zwei Fußnoten. Das Einfügen und Löschen von Elementen in verketteten Listen hat nur dann eine Laufzeitkomplexität von O(1), wenn der Knoten bereits vorhanden ist. Bei einer Hashtabelle kann die Laufzeitkomplexität hingegen auf O(n) ansteigen, wenn viele Schlüssel kollidieren.
Sortieralgorithmen variieren genauso stark:
| Sortieralgorithmus | Am besten | Durchschnitt | Am schlimmsten | Hilfsraum |
|---|---|---|---|---|
| Bubble Sort | An) | O(n²) | O(n²) | O(1) |
| Merge-Sort | O(n log n) | O(n log n) | O(n log n) | An) |
| Schnellsortierung | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Heapsortierung | O(n log n) | O(n log n) | O(n log n) | O(1) |
Mergesort ist vorhersehbar, benötigt aber mehr Speicher. Heapsort sortiert direkt am Speicher und behält den gleichen Worst-Case-Wert bei. Quicksort ist trotz des unschöneren oberen Bereichs in der Praxis meist die bessere Wahl.
Zeitkomplexität in Blockchain und Smart Contracts
Jetzt wird es interessant. Auf dem eigenen Server verschwendet ein ineffizienter Algorithmus CPU-Leistung und kann Nutzer verärgern. Auf Ethereum oder einer anderen EVM-Blockchain hingegen kostet er Geld. Jeder von einem Smart Contract ausgeführte Opcode verursacht Gaskosten, die in der jeweiligen Blockchain-Währung bezahlt werden. Die Anzahl der Operationen schlägt sich also in der Rechnung nieder. Kurz gesagt: Eine schlechte Zeitkomplexität hat ihren Preis.
Angenommen, Sie haben einen Vertrag, der alle Token-Inhaber durchläuft, um Belohnungen auszuzahlen. Dabei steigen die Gaskosten mit jedem neuen Inhaber. Am Starttag bemerkt das niemand.
Die Liste der Inhaber wächst unaufhörlich. Eines Tages benötigt die Auszahlung mehr Gas, als das Block-Gaslimit – die maximale Gasmenge, die in einen einzelnen Block passen darf – zulässt. Danach kann die Transaktion nicht mehr durchgeführt werden. Nicht etwa, weil sie zu langsam ist. Sie schlägt einfach fehl, und die Gelder, die hinter dieser Funktion standen, sind praktisch blockiert. Prüfer stufen solche Endlosschleifen als Denial-of-Service ein, und das völlig zu Recht.
Die Lösung liegt im Komplexitätsdenken, ganz einfach:
- Die Arbeit wird in Teilstücke fester Größe über mehrere Transaktionen aufgeteilt.
- Drehen Sie es um, sodass jeder Benutzer seine eigene Belohnung erhält. Jeder Aufruf ist O(1).
- Ersetze die Schleife durch einen Merkle-Beweis.
Ich liebe Merkle-Beweise als Beispiel dafür, warum log n auf der Blockchain so wichtig ist. Ein Merkle-Baum reduziert einen großen Datenstapel auf einen einzigen Wurzel-Hash.
Um zu beweisen, dass ein Eintrag zu einer Menge von n Einträgen gehört, benötigt man etwa log₂(n) Hashes. Bei einer Million Einträgen sind das ungefähr 20. Nicht eine Million. Airdrops nutzen dieses Prinzip, und schlanke Bitcoin-Wallets verwenden denselben Trick, um eine Transaktion zu bestätigen, ohne den gesamten Block herunterzuladen.
Off-Chain gilt dasselbe Prinzip. Stellen Sie sich ein Zahlungs-Backend vor, das jede eingehende Blockchain-Transaktion mit einer Rechnung abgleicht, indem es alle offenen Rechnungen scannt. Der Aufwand pro Zahlung beträgt O(n), und mit zunehmender Größe des Shops sinkt die Geschwindigkeit. Speichert man die Rechnungen in einer Hash-Map, die nach Adresse oder ID indiziert ist, ist jeder Abgleich O(1). Und falls Sie diese Infrastruktur nicht selbst entwickeln und betreuen möchten, übernimmt ein Krypto-Zahlungsgateway wie Plisio diese Aufgabe für Sie.
