O-Notation (Big O)
Die Kurzantwort · 18 Wörter
Kurz erklärt
Mathematische Notation zur Beschreibung einer asymptotischen oberen Schranke für das Wachstum von Aufwand oder Funktionen bei zunehmender Eingabegröße.
Flow-alerta.cab (2026): O-Notation (Big O). https://flow-alerta.cab/glossar/big-o-notation. Redaktionell geprüft am: 09. Oktober 2026.
Wie ausführlich soll es sein?
Praxis
Grundlage für algorithmische Skalierbarkeit und technische Architekturentscheidungen. Besonders nützlich beim Vergleich von Such-, Sortier- und Datenstrukturalgorithmen.
Beispielszenario: Binäre Suche benötigt in einer sortierten Liste logarithmisch wachsende Suchschritte und wird typischerweise mit O(log n) beschrieben.
Bei Software mit großen Datenmengen nutzen, um früh zu erkennen, welche Algorithmen oder Datenzugriffe schlecht skalieren könnten; anschließend reale Messungen ergänzen.
Auf einen Blick
- Kern
- In der Informatik wird Big O häufig genutzt, um zu beschreiben, wie Zeit- oder Speicherbedarf eines Algorithmus mit der Problemgröße wächst. Formal bedeutet f(n)=O(g(n)), dass f ab einer hinreichend großen Eingabe durch ein konstantes Vielfaches von g nach oben beschränkt ist. Umgangssprachlich wird Big O oft ungenau als exakte Laufzeitklasse verwendet.
- Nutzen
- Grundlage für algorithmische Skalierbarkeit und technische Architekturentscheidungen. Besonders nützlich beim Vergleich von Such-, Sortier- und Datenstrukturalgorithmen.
- Beispiel
- Beispielszenario: Binäre Suche benötigt in einer sortierten Liste logarithmisch wachsende Suchschritte und wird typischerweise mit O(log n) beschrieben.
- Grenzen
- Big O als exakte Laufzeit verstehen; Konstanten und reale Hardware komplett ignorieren; O und Θ gleichsetzen; Durchschnitts- und Worst-Case nicht unterscheiden.
Fragen, die dazu gestellt werden
Misst Big O reale Sekunden? Nein. Ist ein mit O(n²) beschriebener Algorithmus immer langsamer als einer mit O(n)? Nein; O gibt nur obere Schranken an. Für einen belastbaren Vergleich braucht man passend enge Schranken und konkrete Bedingungen. Ist O dasselbe wie Θ? Nein.
Alle Details und Hintergründe
In der Informatik wird Big O häufig genutzt, um zu beschreiben, wie Zeit- oder Speicherbedarf eines Algorithmus mit der Problemgröße wächst. Formal bedeutet f(n)=O(g(n)), dass f ab einer hinreichend großen Eingabe durch ein konstantes Vielfaches von g nach oben beschränkt ist. Umgangssprachlich wird Big O oft ungenau als exakte Laufzeitklasse verwendet.
ELI5 – Einfach erklärt
Big O beschreibt nicht die Sekunden auf einem bestimmten Rechner, sondern wie stark der Aufwand wächst, wenn die Eingabe größer wird.
Warum das im Alltag wichtig ist
Grundlage für algorithmische Skalierbarkeit und technische Architekturentscheidungen. Besonders nützlich beim Vergleich von Such-, Sortier- und Datenstrukturalgorithmen.
Beispiel
Beispielszenario: Binäre Suche benötigt in einer sortierten Liste logarithmisch wachsende Suchschritte und wird typischerweise mit O(log n) beschrieben.
Fallstricke und Grenzen
- Big O als exakte Laufzeit verstehen; Konstanten und reale Hardware komplett ignorieren; O und Θ gleichsetzen; Durchschnitts- und Worst-Case nicht unterscheiden.
Entstehung & Geschichte
Das NIST-Wörterbuch definiert O-Notation als asymptotische obere Schranke. Eine enge asymptotische Schranke wird mit Θ bezeichnet; O legt allein keine exakte Wachstumsrate fest.
Anwendung im Mittelstand
- Bei Software mit großen Datenmengen nutzen, um früh zu erkennen, welche Algorithmen oder Datenzugriffe schlecht skalieren könnten; anschließend reale Messungen ergänzen.
Verwandte Begriffe
- Zeitkomplexität
- Speicherkomplexität
Passende Flow-alerta-Leistung
Websites & Web-AnwendungenWebsites & Web-Anwendungen: technische Umsetzung und Prüfung einer passenden Webanwendung.Passendes Tool / Use Case
Praxisbeispiele ansehenUse Case: Vergleich der Skalierung zweier Such- oder Verarbeitungsalgorithmen.Quellen
- xlinux.nist.govNIST Dictionary of Algorithms and Data Structures, big-O notation
Quellenprüfung: 09.10.2026. Definition und dokumentierte Einordnung abgeglichen; Beispiele beschreiben mögliche Anwendungen.
Redaktionell geprüft am: