Landau-Symbole O(1) bis O(n²), Divide-and-Conquer, Quicksort vs. Mergesort & Binäre Suche.
Prüfungsbereich 2 (Entwicklung und Umsetzung von Algorithmen): Asymptotische Laufzeitkomplexität, Divide-and-Conquer, Sortier- und Suchverfahren.
| Komplexität | Bezeichnung | Typisches Beispiel | Skalierbarkeit |
|---|---|---|---|
| $O(1)$ | Konstant | Array-Indexzugriff, HashMap get(key), Push/Pop auf Stack | Optimal |
| $O(\log n)$ | Logarithmisch | Binäre Suche im sortierten Array, Suchen im balancierten AVL-Baum | Exzellent |
| $O(n)$ | Linear | Lineare Suche in Liste, Minimum/Maximum finden | Gut |
| $O(n \log n)$ | Linear-logarithmisch | Mergesort, Quicksort (Average-Case), Heapsort | Sehr gut |
| $O(n^2)$ | Quadratisch | Bubblesort, Insertionsort, verschachtelte Doppelschleifen | Schlecht bei großem $n$ |
| $O(2^n)$ | Exponentiell | Brute-Force Knapsack-Problem, naive rekursive Fibonacci-Zahlen | Inakzeptabel |
- Quicksort (In-Place): Wählt ein Pivot-Element, partitioniert das Array in kleinere und größere Werte und sortiert rekursiv. Average-Case $O(n \log n)$, Worst-Case $O(n^2)$ bei unglücklicher Pivot-Wahl.
- Mergesort (Stabil): Teilt das Array wiederholt in zwei Hälften bis zur Elementlänge 1 und verschmilzt (Merge) sie sortiert. Garantiert immer $O(n \log n)$, benötigt aber $O(n)$ zusätzlichen Speicher.
Bearbeiten Sie die Aufgaben und vergleichen Sie Ihre Antwort mit dem didaktischen Erwartungshorizont:
Erklären Sie die Landau-Symbole (O-Notation) zur Abschätzung der Zeitkomplexität. Ordnen Sie folgende Komplexitätsklassen von der effizientesten zur ineffizientesten Laufzeit: O(n log n), O(1), O(n²), O(log n), O(n). Nennen Sie je ein typisches Code- oder Algorithmenbeispiel für O(1), O(log n) und O(n).
Vergleichen Sie Quicksort und Mergesort nach dem Divide-and-Conquer-Prinzip hinsichtlich Best-Case-, Average-Case- und Worst-Case-Laufzeit, Speicherplatzkomplexität und Stabilität.