Big O Notation: Grundlegende Konzepte

2.1 Definition der Big O Notation.

Die Big O Notation ist eine mathematische Notation, die verwendet wird, um die obere Grenze der Laufzeit oder des Ressourcenverbrauchs eines Algorithmus in Abhängigkeit von der Größe der Eingabedaten zu beschreiben. Sie hilft dabei zu bestimmen, wie gut ein Algorithmus skaliert und wie sich seine Leistung bei wachsendem Datenvolumen ändert.

Die Big O Notation konzentriert sich auf die bedeutendsten Aspekte eines Algorithmus, indem sie Konstanten und weniger bedeutende Terme ignoriert, was es ermöglicht, sich auf das langfristige Verhalten des Algorithmus zu fokussieren.

Grundlegende Notationen:

O(1) — Konstante Komplexität:

• Die Laufzeit des Algorithmus hängt nicht von der Größe der Eingabedaten ab.
• Beispiel: Zugriff auf ein Array-Element per Index.

O(n) — Lineare Komplexität:

• Die Laufzeit des Algorithmus ist linear abhängig von der Größe der Eingabedaten.
• Beispiel: einfaches Durchlaufen aller Elemente eines Arrays.

O(log n) — Logarithmische Komplexität:

• Die Laufzeit des Algorithmus wächst logarithmisch mit der Zunahme der Eingabedaten.
• Beispiel: Binäre Suche in einem sortierten Array.

O(n^2) — Quadratische Komplexität:

• Die Laufzeit des Algorithmus ist quadratisch abhängig von der Größe der Eingabedaten.
• Beispiel: Bubblesort, Insertionsort.

O(2^n) — Exponentielle Komplexität:

• Die Laufzeit des Algorithmus ist exponentiell abhängig von der Größe der Eingabedaten.
• Beispiel: Lösung des Rucksackproblems durch vollständige Enumeration.

2.2 Interpretation der Big O Notation.

Wie interpretiert und verwendet man die Big O Notation?

Ignorieren von Konstanten und weniger bedeutenden Termen:

Big O beschreibt das Wachstumsverhalten einer Funktion und ignoriert dabei Konstanten und weniger bedeutende Terme. Zum Beispiel werden O(2n) und O(3n) als O(n) interpretiert.

Vergleich von Algorithmen:

Big O ermöglicht den Vergleich von Algorithmen basierend auf ihrer asymptotischen Effizienz. Beispielsweise ist ein Algorithmus mit O(n log n) effizienter als ein Algorithmus mit O(n^2) für sehr große Datenmengen.

Analyse des schlimmsten Falls:

Big O wird normalerweise zur Analyse der Laufzeit eines Algorithmus im schlimmsten Fall verwendet, was die Bewertung seiner maximalen Komplexität ermöglicht.

Ignorieren von Konstanten.

Ignorieren von Konstanten und weniger bedeutenden Termen

Beispiel 1:

Betrachten wir zwei Funktionen:

• f(n) = 3n + 2
• g(n) = 5n + 1

Beide Funktionen haben eine lineare Komplexität, da der dominierende Term in jeder Funktion n ist. Daher werden beide Funktionen als O(n) interpretiert, trotz der Unterschiede in den Koeffizienten und Zusatzelementen.

Beispiel 2:

Betrachten wir zwei Funktionen:

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

Beide Funktionen haben eine quadratische Komplexität, da der dominierende Term n^2 ist. Beide Ausdrücke werden als O(n^2) interpretiert, trotz der Unterschiede in den anderen Termen und Koeffizienten.

2.3. Vergleich von Algorithmen

1. Vergleich von Algorithmen bei sehr großen Datenmengen

Beispiel 1:

• Algorithmus A hat eine zeitliche Komplexität von O(n^2).
• Algorithmus B hat eine zeitliche Komplexität von O(n log n).

Bei kleinen Werten von n kann Algorithmus A aufgrund kleinerer Konstanten schneller arbeiten, aber bei großen Werten von n wird Algorithmus B deutlich schneller sein, da sein Wachstum logarithmisch und nicht quadratisch ist.

Beispiel 2:

• Algorithmus X hat eine zeitliche Komplexität von O(n).
• Algorithmus Y hat eine zeitliche Komplexität von O(1).

Algorithmus Y wird immer schneller sein, unabhängig von der Größe von n, da O(1) bedeutet, dass die Laufzeit des Algorithmus nicht von der Größe der Eingabedaten abhängt.

2. Analyse des schlimmsten Falls

Beispiel 1:

Der Bubblesort-Algorithmus hat im schlimmsten Fall eine zeitliche Komplexität von O(n^2), wenn das Array in umgekehrter Reihenfolge sortiert ist. Das bedeutet, dass für jedes Element im Array ein Vergleich und eventuell ein Tausch mit jedem anderen Element erforderlich ist.

Beispiel 2:

Die binäre Suche hat im schlimmsten Fall eine zeitliche Komplexität von O(log n). Das bedeutet, dass selbst im schlimmsten Fall die Anzahl der Schritte, die erforderlich sind, um ein Element zu finden, logarithmisch vom Array-Umfang abhängt, was sehr effizient ist.

3. Auswirkungen auf die Leistung und Skalierbarkeit

Beispiel 1:

Wenn wir zwei Algorithmen zur Datenverarbeitung haben, einer mit der zeitlichen Komplexität O(n^2) und der andere mit O(n log n), und wir die Datenmenge von 1000 auf 10,000 Elemente erhöhen, wird der Leistungsunterschied deutlich spürbar sein.

• Der Algorithmus mit O(n^2) wird etwa 100.000.000 Operationen für 10.000 Elemente ausführen.
• Der Algorithmus mit O(n log n) wird etwa 40.000 Operationen für 10.000 Elemente ausführen.

Beispiel 2:

Betrachten wir einen Algorithmus, der in O(2^n) arbeitet. Wenn wir die Eingabedaten von 10 auf 20 Elemente erhöhen, steigt die Anzahl der Operationen exponentiell an.

• Für n = 10: 2^10 = 1024 Operationen.
• Für n = 20: 2^20 = 1.048.576 Operationen.

Das zeigt, wie schnell exponentielle Komplexität für große Werte von n unpraktisch wird.