23e9820aad49ba7ce68630a3ab42abd2.jpeg

## Algorithmen und Datenstrukturen ### Komplexität #### Landau-Symbole Die Landau-Symbole (auch O-Notation genannt) werden verwendet, um das asymptotische Verhalten einer Funktion zu beschreiben. Sie geben an, wie schnell eine Funktion wächst, wenn sich ihr Eingabewert (z. B. die Größe eines Arra...

## Algorithmen und Datenstrukturen ### Komplexität #### Landau-Symbole Die Landau-Symbole (auch O-Notation genannt) werden verwendet, um das asymptotische Verhalten einer Funktion zu beschreiben. Sie geben an, wie schnell eine Funktion wächst, wenn sich ihr Eingabewert (z. B. die Größe eines Arrays) einem Grenzwert nähert. - **Definition:** Seien $f,g: \mathbb{N} \rightarrow \mathbb{R}^{+}$ Funktionen, dann gilt: * $f(n) \in O(g(n))$: Es existieren positive Konstanten $c$ und $n_0$, so dass $f(n) \le c \cdot g(n)$ für alle $n \ge n_0$ * $f(n) \in \Omega(g(n))$: Es existieren positive Konstanten $c$ und $n_0$, so dass $f(n) \ge c \cdot g(n)$ für alle $n \ge n_0$ * $f(n) \in \Theta(g(n))$: Es existieren positive Konstanten $c_1, c_2$ und $n_0$, so dass $c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ für alle $n \ge n_0$ * $f(n) \in o(g(n))$: Für alle positiven Konstanten $c$ existiert eine Konstante $n_0$, so dass $f(n) < c \cdot g(n)$ für alle $n \ge n_0$ * $f(n) \in \omega(g(n))$: Für alle positiven Konstanten $c$ existiert eine Konstante $n_0$, so dass $f(n) > c \cdot g(n)$ für alle $n \ge n_0$ - **Übliche Komplexitätsklassen** | Notation | Bezeichnung | Beispiel | | :---------------- | :------------- | :------------------------------ | | $O(1)$ | konstant | Array-Zugriff | | $O(log \ n)$ | logarithmisch | Binäre Suche | | $O(n)$ | linear | Lineare Suche | | $O(n \ log \ n)$ | "n log n" | Mergesort | | $O(n^2)$ | quadratisch | Einfache Sortieralgorithmen | | $O(n^3)$ | kubisch | Matrixmultiplikation | | $O(2^n)$ | exponentiell | Brute-Force-Suche | | $O(n!)$ | faktoriell | Permutationen generieren | - **Rechenregeln** * **Konstanter Faktor:** $O(c \cdot f(n)) = O(f(n))$ * **Summe:** $O(f(n) + g(n)) = O(max(f(n), g(n)))$ * **Produkt:** $O(f(n) \cdot g(n)) = O(f(n)) \cdot O(g(n))$ * **Transitivität:** * Wenn $f(n) \in O(g(n))$ und $g(n) \in O(h(n))$, dann $f(n) \in O(h(n))$ * Wenn $f(n) \in \Omega(g(n))$ und $g(n) \in \Omega(h(n))$, dann $f(n) \in \Omega(h(n))$ * Wenn $f(n) \in \Theta(g(n))$ und $g(n) \in \Theta(h(n))$, dann $f(n) \in \Theta(h(n))$ #### Speicherkomplexität Die Speicherkomplexität beschreibt, wie viel Speicherplatz ein Algorithmus in Abhängigkeit von der Eingabegröße benötigt. Auch hier werden die Landau-Symbole verwendet.