Big O Notation
Die Big-O-Notation beschreibt die asymptotische obere Schranke einer Funktion und dient der Analyse der Zeit-/Speicherkomplexität von Algorithmen unter Vernachlässigung von Konstanten und niedrigeren Termen.
Zweck
Die asymptotische Wachstumsrate der Algorithmuseffizienz abstrahieren, um Algorithmen zu vergleichen und auszuwählen.
Mechanismus
f(n)=O(g(n)) bedeutet: Es gibt Konstanten C und n0, sodass |f(n)|≤C|g(n)| für alle n>n0. Übliche Ordnungen: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!). Der Fokus liegt auf oberen Schranken im Worst Case.
Anwendungsfälle
- Analyse der Algorithmuskomplexität
- Auswahl von Datenstrukturen
- Entscheidungen zur Leistungsoptimierung
- Vorstellungsgespräche und Lehre
Beispiele
- Eingabe
Binary searchOutputO(log n)Halves each time
Häufige Fehler
- Ignoring constant factors misjudges real-world performance
- Big O is asymptotic; benchmark for real behavior
Verwandte Begriffe
Sorting Algorithm
Sortieralgorithmen bringen Elemente in eine Reihenfolge — Quicksort, Mergesort und Heapsort sind verbreitet — mit Komplexitäten von O(n log n) bis O(n²). GLOSSAR
Binary Search
Die binäre Suche vergleicht mit dem mittleren Element eines sortierten Arrays und halbiert den Bereich jedes Mal, wodurch ein Ziel in O(log n) gefunden wird; sie ist der grundlegende effiziente Suchalgorithmus. GLOSSAR
Hash Table
Eine Hashtabelle bildet Schlüssel über eine Hashfunktion auf ein Bucket-Array ab und bietet im Schnitt O(1) bei Suche/Einfügen/Löschen; sie gehört zu den meistgenutzten Datenstrukturen. GLOSSAR