Zwei Codestücke können bei einem kleinen Testfall identische Ergebnisse liefern und sich völlig unterschiedlich verhalten, sobald echte Daten eintreffen. Die Big-O-Notation ist die Art, wie Informatiker diesen Unterschied präzise beschreiben — indem sie mathematisch beschreibt, wie die Anzahl der Operationen wächst, während die Eingabegröße zunimmt.
A-Level-Vertiefung
Was das „O“ wirklich bedeutet
Big O beschreibt die Wachstumsrate eines Algorithmus — wie die Anzahl der Operationen wächst, während die Eingabegröße, traditionell n genannt, zunimmt. Es ignoriert absichtlich konstante Faktoren und kleine Terme, da die Frage, die es beantworten soll, „wie wächst das“ ist, eine Frage, deren Antwort nicht davon abhängt, auf welchem Computer Sie es ausführen.
Die Wachstumsraten, die wirklich zählen
Eine Handvoll Wachstumsraten deckt fast jeden Algorithmus ab, dem Sie begegnen werden, vom besten zum schlechtesten, während Daten wachsen:
- O(1) — konstant. Gleiche Anzahl von Schritten unabhängig von der Eingabegröße, wie zu prüfen, ob eine Liste leer ist.
- O(log n) — logarithmisch. Operationen wachsen sehr langsam, während n zunimmt — zum Beispiel binäre Suche in einer sortierten Liste.
- O(n) — linear. Verdoppeln Sie die Eingabe, verdoppeln Sie die Arbeit — wie einmal jedes Element einer unsortierten Liste zu durchlaufen.
- O(n²) — quadratisch. Verdoppeln Sie die Eingabe, die Arbeit vervierfacht sich — typisch beim Vergleich jedes Elements mit jedem anderen Element.
Für ein kleines n ähneln sich diese Kurven — der Unterschied, der bestimmt, welcher Algorithmus echte Daten der realen Welt tatsächlich übersteht, erscheint erst, wenn n groß wird, und genau diesen Bereich soll Big O beschreiben.
Try it yourself — drag the slider to change the input size (n), and watch how many operations each growth rate actually needs.
Input size: n = 10
At n = 10, an O(n²) approach needs 100 operations — 10× more than the O(n) approach doing the exact same job.
Ein quadratischer Algorithmus, O(n²), der 100 Operationen für 10 Elemente ausführt, führt 1.000.000 für 1.000 Elemente aus — nicht 100-mal mehr Arbeit für 100-mal mehr Daten, sondern 10.000-mal mehr.
Prüfungsähnliche Frage
Ein Algorithmus benötigt 8 Operationen für 4 Elemente, 32 Operationen für 8 Elemente und 128 Operationen für 16 Elemente. Bestimmen Sie seine Big-O-Wachstumsrate und zeigen Sie Ihre Überlegung. [3 Punkte]
Musterantwort und Punkteverteilung anzeigen
- Vergleichen Sie aufeinanderfolgende Fälle, in denen sich n verdoppelt: 4 → 8 und 8 → 16 (1 Punkt)
- Die Anzahl der Operationen vervierfacht sich jedes Mal: 8 → 32 (×4) und 32 → 128 (×4) (1 Punkt)
- Wenn eine Verdopplung von n dazu führt, dass sich die Operationsanzahl vervierfacht (×4 = ×2²), ist dies das Kennzeichen von quadratischem Wachstum: O(n²) (1 Punkt)
Worauf der Prüfer achtet: identifizieren Sie das spezifische Muster zwischen Verdopplungen von n und dem resultierenden Multiplikator der Operationen — dieses Verhältnis (hier ×4 pro Verdopplung) identifiziert tatsächlich die Wachstumsrate, nicht die reinen Zahlen für sich genommen.
Häufiger Fehler: lineares Wachstum anzunehmen, nur weil die Zahlen „konstant größer werden“, ohne die Verdopplungsbeziehung zu prüfen, die O(n) (×2 pro Verdopplung von n) von O(n²) (×4 pro Verdopplung) unterscheidet.
Warum der Unterschied zwischen Wachstumsraten in der Praxis zählt
Bei kleinen Testdaten können sowohl ein O(n²)- als auch ein O(n log n)-Algorithmus beide in einem Bruchteil einer Sekunde fertig sein — der Unterschied ist unsichtbar. Lassen Sie dieselbe Eingabe auf die Größe wachsen, die ein echtes Produkt tatsächlich verarbeitet, und der O(n²)-Ansatz kann echte Stunden brauchen, wo der O(n log n)-Ansatz Sekunden braucht.
Warum das über das Schreiben korrekten Codes hinaus zählt
Jeder Programmierer kann Code schreiben, der die richtige Antwort liefert. Wenn Informatik etwas ist, das Sie oder Ihr Kind verstehen sollten, indem erklärt wird, warum ein Ansatz besser ist als ein anderer, nicht nur die Syntax, ist genau dafür unsere GCSE- und A-Level-Informatik-Nachhilfe da, und Sie können den vollständigen Lernweg hier sehen.
Häufig gestellte Fragen
Warum ignorieren wir Konstanten und kleine Terme — geht dabei nicht nützliche Information verloren?
Big O ist absichtlich entworfen, um eine spezifische Frage zu beantworten — wie wächst die Laufzeit, wenn die Eingabe sehr groß wird — und je größer n, desto weniger zählen Konstanten. Big O erzählt nicht die ganze Leistungsgeschichte, aber es sagt korrekt vorher, welcher Algorithmus gewinnt, sobald die Daten groß genug sind.
Ist ein niedrigeres Big O in der Praxis immer die bessere Wahl?
Nicht automatisch — bei kleinen Eingaben kann ein Algorithmus mit schlechterem Big O, aber weit kleinerem konstanten Faktor tatsächlich in der Praxis schneller laufen, da der Kreuzungspunkt, an dem der „bessere“ Algorithmus zu gewinnen beginnt, erst bei einem weit größeren n eintreten kann.
Wie wird Big O tatsächlich täglich von Programmierern genutzt, nicht nur im Vorstellungsgespräch?
Es ist die Art, wie ein Entwickler vorhersagt, ob ein Ansatz noch funktioniert, sobald echte (sehr große) Daten eintreffen. Die Suche in einer unsortierten Liste ist O(n); binäre Suche in einer sortierten Liste ist O(log n) — ein unsichtbarer Unterschied bei 10 Elementen und ein enormer bei 10 Millionen.
Bewertungen und Rezensionen von Lesern
Bewerten Sie diesen Artikel in mehreren Kategorien — Ihre Rückmeldung hilft anderen Lesern und uns bei der Verbesserung.
War dieser Artikel hilfreich für Sie?
Sagen Sie uns, was Sie denken — eine Korrektur, eine unbeantwortete Frage, oder ein Thema, das Sie als Nächstes behandelt sehen möchten.
Lieber persönlich sprechen? Buchen Sie ein kostenloses Videogespräch zu einer passenden Zeit: 15 Minuten für eine kurze Frage, 30 für alles andere. Die Zeiten erscheinen in Ihrer Zeitzone.
Über den Autor
Sudershan Soni
Gründer und leitender Tutor bei Mostak Services — Tutor für Mathematik, Naturwissenschaften, Informatik und MINT mit Master-Abschluss und über 20 Jahren Berufserfahrung, unterrichtet Schüler von der 11+-Prüfung und GCSE bis zum A-Level und darüber hinaus, online weltweit.
Vollständiges Profil lesen