Programmierung · Konzepte · Algorithmen
Was ist die Big-O-Notation?
Die Big-O-Notation ist eine Moeglichkeit zu beschreiben, wie die Laufzeit (oder der Speicherverbrauch) eines Algorithmus waechst, wenn seine Eingabe groesser wird. Sie beantwortet eine Frage: Wenn sich die Datenmenge verdoppelt oder vertausendfacht, bleibt dein Code schnell, wird er ein wenig langsamer oder kommt er ganz zum Stillstand? Sie ignoriert bewusst genaue Sekunden und Maschinengeschwindigkeit und konzentriert sich auf die Form des Wachstums - denn das entscheidet, ob Code, der bei 100 Elementen funktioniert, auch bei 100 Millionen noch funktioniert.
Warum nicht einfach die Zeit messen?
Weil Sekunden von der Maschine, der Sprache, dem Compiler und davon abhaengen, was sonst noch laeuft. Fuehre denselben Code auf einem Laptop und auf einem Server aus, und du erhaeltst unterschiedliche Zahlen. Big O wirft all das weg und misst etwas Bestaendigeres: wie die Arbeit mit der Eingabegroesse skaliert, die ueblicherweise n genannt wird. Zwei Algorithmen koennen beide "ein paar Millisekunden" bei kleiner Eingabe brauchen, doch der eine bleibt bei grossen Datenmengen schnell, waehrend der andere unbrauchbar wird. Big O ist die Art, wie wir sie unterscheiden, bevor wir gegen diese Wand laufen.
Die gaengigen Komplexitaeten, von der besten zur schlechtesten
Das sind die Wachstumsraten, denen du am haeufigsten begegnest, von der am besten skalierenden bis zur gefaehrlichsten:
| Notation | Name | Grobe Idee |
|---|---|---|
| O(1) | Konstant | Gleiche Arbeit unabhaengig von der Eingabegroesse - z. B. das Lesen von array[5]. |
| O(log n) | Logarithmisch | Halbiert das Problem bei jedem Schritt - z. B. die binaere Suche. |
| O(n) | Linear | Die Arbeit waechst im Gleichschritt mit der Eingabe - z. B. das einmalige Durchgehen einer Liste. |
| O(n log n) | Linearithmisch | Das Beste, was fuer allgemeines Sortieren moeglich ist - z. B. mergesort. |
| O(n²) | Quadratisch | Eine Schleife in einer Schleife - in Ordnung bei 100 Elementen, schmerzhaft bei einer Million. |
| O(2ⁿ) | Exponentiell | Verdoppelt sich mit jedem hinzugefuegten Element - nur bei winzigen Eingaben nutzbar. |
| O(n!) | Faktoriell | Jede Anordnung der Eingabe - praktikabel nur fuer sehr kleines n. |
Warum Konstanten und kleine Terme weggelassen werden
Big O kuemmert sich um das Wachstum, nicht um genaue Anzahlen, also vereinfacht es. Wenn ein Algorithmus 2n + 3 Schritte ausfuehrt, wird das als O(n) geschrieben: Die 2 und die 3 aendern die Form der Kurve nicht, wenn n gross wird. Ebenso wird n² + n zu O(n²), weil der quadratische Term dominiert, sobald n gross ist. Deshalb geht es bei Big O um den dominanten Term - den Teil, der das Verhalten bei grossen Datenmengen bestimmt - und nicht um eine genaue Stoppuhr-Anzeige.
Ein konkretes Beispiel
Angenommen, du willst pruefen, ob eine Liste ein Duplikat enthaelt. Ein Ansatz vergleicht jedes Element mit jedem anderen Element - zwei verschachtelte Schleifen, ungefaehr n × n Vergleiche, also O(n²). Ein anderer Ansatz fuegt jedes Element einem hash set hinzu und prueft dabei die Mitgliedschaft - ein Durchlauf, also O(n). Bei 1.000 Elementen macht die quadratische Variante etwa eine Million Vergleiche; bei 100.000 Elementen macht sie zehn Milliarden, waehrend die lineare Variante 100.000 macht. Dieselbe Aufgabe, voellig unterschiedliches Schicksal bei grossen Datenmengen. Genau diese Luecke soll Big O sichtbar machen.
Schlechtester, durchschnittlicher und bester Fall
Streng genommen beschreibt Big O eine obere Schranke - meist den schlechtesten Fall, die meiste Arbeit, die der Algorithmus leisten koennte. Du wirst auch zwei Verwandte sehen: Big Omega (Ω) fuer den besten Fall, eine untere Schranke, und Big Theta (Θ), wenn der beste und der schlechteste Fall gleich schnell wachsen und damit eine enge Schranke ergeben. Im Alltag sagen die Leute locker "Big O" und meinen damit das Wachstum im schlechtesten Fall, denn das ist es, worauf man plant: Du willst wissen, wie schlimm es werden kann, nicht wie viel Glueck du gelegentlich haben koenntest.
Auch die Speicherkomplexitaet
Dieselbe Notation beschreibt Speicher, nicht nur Zeit. Ein Algorithmus, der die gesamte Eingabe in eine neue Struktur kopiert, verbraucht O(n) zusaetzlichen Speicher; einer, der die Eingabe an Ort und Stelle umordnet, verbraucht O(1) zusaetzlichen Speicher. Bei grossen Datenmengen kann der Speicher die eigentliche Grenze sein, daher lohnt es sich, beides zu fragen: "Wie waechst die Zeit?" und "Wie waechst der Speicher?"
Wie du deinen eigenen Code einschaetzt
- Zaehle die Schleifen ueber die Eingabe. Ein Durchlauf ist meist O(n); eine Schleife in einer Schleife ueber dieselben Daten ist meist O(n²).
- Halbieren ist ein Logarithmus. Wenn jeder Schritt die Haelfte der verbleibenden Daten verwirft (wie die binaere Suche), ist das O(log n).
- Nachschlagen in einer hash map/einem hash set ist ~O(1). Eine verschachtelte Durchsuchung durch ein hash lookup zu ersetzen ist der klassische Weg, um O(n²) in O(n) zu verwandeln.
- Lass die Konstanten weg. Drei getrennte einzelne Durchlaeufe sind immer noch O(n), nicht O(3n) - auf die Form kommt es an.
FAQ
Ist ein niedrigeres Big O immer schneller? Bei grossen Datenmengen ja - aber nicht immer bei kleinen Eingaben. Konstanten und Overhead, die Big O ignoriert, koennen dazu fuehren, dass eine O(n²)-Methode eine O(n log n)-Methode bei einer Handvoll Elemente schlaegt. Big O sagt dir, wer gewinnt, wenn die Daten waechsen, und das ist meist das, worauf es ankommt.
Was ist die bestmoegliche Komplexitaet? O(1), konstante Zeit - die Arbeit waechst ueberhaupt nicht mit der Eingabe. Am zweitbesten ist O(log n). Fuer Probleme, die jedes Element mindestens einmal ansehen muessen, ist O(n) die Untergrenze.
Warum ist O(n log n) beim Sortieren besonders? Es ist die bewiesene untere Schranke fuer allgemeines vergleichsbasiertes Sortieren, daher zielen mergesort, heapsort und gute quicksort-Implementierungen alle darauf ab. Beliebige Daten lassen sich mit Vergleichen allein im Allgemeinen nicht schneller sortieren.
Brauche ich Big O fuer die alltaegliche Programmierung? Du brauchst nicht die formale Mathematik, aber die Intuition ist unbezahlbar: zu erkennen, wann eine verschachtelte Schleife bei grosser Eingabe explodiert oder wann ein hash lookup dich rettet, verhindert ganze Klassen von Performance-Bugs.