Big O Notation

11.1 Definition der Big O-Notation

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

Die Big O-Notation konzentriert sich auf die wichtigsten Aspekte eines Algorithmus und ignoriert Konstanten und weniger wichtige Terme, um sich auf das langfristige Verhalten des Algorithmus zu fokussieren.

Hauptnotationen:

O(1) — Konstante Komplexität:

• Die Ausführungszeit 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 Ausführungszeit des Algorithmus hängt linear von der Größe der Eingabedaten ab.
• Beispiel: Einfaches Durchlaufen aller Elemente eines Arrays.

O(log n) — Logarithmische Komplexität:

• Die Ausführungszeit des Algorithmus wächst logarithmisch mit zunehmender Größe der Eingabedaten.
• Beispiel: Binäre Suche in einem sortierten Array.

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

• Die Ausführungszeit des Algorithmus hängt quadratisch von der Größe der Eingabedaten ab.
• Beispiel: Bubblesort, Insertsort.

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

• Die Ausführungszeit des Algorithmus hängt exponentiell von der Größe der Eingabedaten ab.
• Beispiel: Lösung des Rucksackproblems durch vollständiges Durchprobieren.

Hinweis. Mehr über die binäre Suche, Bubblesort und das „Rucksackproblem“ erfährst du in den folgenden Vorlesungen.

11.2 Interpretation der Big O-Notation

Wie interpretiert und verwendet man die Big O-Notation?

Ignorieren von Konstanten und weniger signifikanten Termen: Big O beschreibt die Wachstumsordnung einer Funktion, indem Konstanten und weniger signifikante Terme ignoriert werden. Zum Beispiel werden O(2n) und O(3n) als O(n) interpretiert.

Vergleich von Algorithmen: Big O ermöglicht den Vergleich von Algorithmen hinsichtlich ihrer asymptotischen Effizienz. Zum Beispiel 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 häufig zur Analyse des schlimmsten Falls der Ausführungszeit eines Algorithmus verwendet, was eine Einschätzung seiner maximalen Komplexität erlaubt.

Ignorieren von Konstanten

Betrachten wir Beispiele zum Ignorieren von Konstanten und weniger signifikanten Termen:

Beispiel 1. Betrachten wir zwei Funktionen:

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

Beide Funktionen haben 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 zusätzlichen Termen.

Beispiel 2. Betrachten wir zwei Funktionen:

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

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

11.3. Vergleich von Algorithmen

1. Vergleich von Algorithmen bei sehr großen Datenmengen

Beispiel 1:

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

Für kleine Werte von n kann Algorithmus A aufgrund geringerer Konstanten schneller arbeiten, aber für große Werte von n wird Algorithmus B erheblich schneller sein, da sein Wachstum logarithmisch und nicht quadratisch ist.

Beispiel 2:

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

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

2. Analyse des schlimmsten Falls

Beispiel 1:

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

Beispiel 2:

Die binäre Suche hat eine Zeitkomplexität von O(log n) im schlimmsten Fall. Das bedeutet, dass selbst im schlimmsten Fall die Anzahl der Schritte, die notwendig sind, um ein Element zu finden, logarithmisch von der Größe des Arrays abhängt, was sehr effizient ist.

3. Einfluss auf Leistung und Skalierbarkeit

Beispiel 1:

Wenn wir zwei Algorithmen zur Datenverarbeitung haben, einen mit einer Zeitkomplexität von O(n^2) und den anderen mit O(n log n), und wir die Datengröße von 1000 Elementen auf 10 000 Elemente erhöhen, wird der Leistungsunterschied erheblich erkennbar sein.

• Der Algorithmus mit O(n^2) wird ungefähr 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) läuft. Wenn wir die Größe der Eingabedaten von 10 auf 20 Elemente erhöhen, steigt die Anzahl der Operationen exponentiell.

• Für n = 10: 2^10 = 1024 Operationen.
• Für n = 20: 2^20 = 1 048 576 Operationen.

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

1

Опрос

Datenstrukturen,  52 уровень,  4 лекция

недоступен

Datenstrukturen

Datenstrukturen

Открыть