Big-O-Notation – Laufzeitkomplexität & Effizienz von Algorithmen

Dieser Beitrag ist eine Begriffserklärung zur Big-O-Notation – inklusive Prüfungsfragen und Tags.

In a Nutshell

Die Big-O-Notation beschreibt, wie stark die Laufzeit oder der Speicherbedarf eines Algorithmus im Verhältnis zur Eingabemenge wächst – sie ist ein Maß für die Effizienz.

Kompakte Fachbeschreibung

Die Big-O-Notation wird verwendet, um die asymptotische Komplexität eines Algorithmus zu analysieren – sie abstrahiert von konkreten Laufzeiten und fokussiert sich auf das Verhalten bei wachsendem Input. Dabei wird im schlimmsten Fall (“Worst Case”) die Anzahl an Rechenschritten oder Speicherzugriffen angegeben, die ein Algorithmus benötigt. Beispiele: O(1) = konstant, O(n) = linear, O(n²) = quadratisch, O(log n) = logarithmisch. So lassen sich Algorithmen unabhängig von Hardware vergleichen.

Prüfungsrelevante Stichpunkte

• Big-O beschreibt das Wachstumsverhalten von Laufzeit/Speicher
• “Worst Case” wird standardmäßig betrachtet
• Typische Notationen: O(1), O(n), O(log n), O(n²), O(n log n)
• Logarithmisch z.B. bei binärer Suche (IHK-relevant)
• Quadratische Algorithmen sind bei großen Daten ineffizient
• Effiziente Algorithmen sparen Ressourcen → wirtschaftlich relevant
• Big-O-Analyse muss in komplexen Algorithmen dokumentiert werden

Kernkomponenten

1. Konstant: O(1)
2. Linear: O(n)
3. Logarithmisch: O(log n)
4. Linear-logarithmisch: O(n log n)
5. Quadratisch: O(n²)
6. Kubisch: O(n³)
7. Exponentiell: O(2ⁿ)
8. Worst-Case-Analyse
9. Best-Case, Average-Case
10. Relevanz für Skalierbarkeit

Praxisbeispiel

// Vergleich: lineare vs. binäre Suche
Lineare Suche: O(n)
Binäre Suche: O(log n), nur bei sortierten Listen

Erklärung: Die lineare Suche durchläuft die Liste vollständig, binäre Suche halbiert das Suchfeld bei jedem Schritt – deutlich effizienter bei großen Datenmengen.

Vorteile und Nachteile

Vorteile

• Vergleichbarkeit von Algorithmen unabhängig von Implementierung
• Erkennung potenzieller Engpässe
• Bessere Entscheidungen in Designphasen

Nachteile

• Keine Aussagen zu konkreten Laufzeiten auf bestimmter Hardware
• Nur Worst-Case ohne Mittelwerte berücksichtigt
• Theoretisch, nicht immer direkt auf reale Bedingungen übertragbar

Typische Prüfungsfragen (mit Kurzantwort)

1. Big-O-Notation beschreibt? Komplexität eines Algorithmus in Bezug auf Laufzeit oder Speicherbedarf bei wachsendem Input.
2. Was bedeutet O(1)? Laufzeit ist konstant – unabhängig von der Eingabegröße.
3. Effizienter: O(n) oder O(log n)? O(log n), da es bei wachsender Datenmenge deutlich schneller ist.
4. Was steht “n” für in O(n)? Anzahl der Eingabeelemente.
5. Algorithmus typischerweise O(n log n)? Merge Sort oder Quick Sort im Durchschnitt.
6. Warum ist O(n²) problematisch? Laufzeit wächst bei großen Datenmengen exponentiell.
7. Gleichzeitig O(n) und O(n²)? Nein – es wird immer die dominante Komponente angegeben.
8. Big-O dokumentieren? Durch Kommentierung im Code, Diagramme oder formale Analyse.

Wichtigste Quellen

1. https://www.bigocheatsheet.com/
2. https://visualgo.net/en
3. https://www.geeksforgeeks.org/analysis-of-algorithms-set-1-asymptotic-analysis/
4. https://cs50.harvard.edu/
5. https://www.youtube.com/results?search_query=big+o+notation