Komplexitätstheorie

Komplexität

In der Informatik spielt die Analyse der Laufzeit und Speicherbedarf von Algorithmen eine wichtige Rolle. Die Komplexitätstheorie ist ein Teilgebiet der Informatik, das sich mit der Untersuchung der Leistungsfähigkeit von Algorithmen beschäftigt.

Sie verwendet verschiedene Methoden, um die Laufzeit von Algorithmen zu beschreiben und zu vergleichen. Diese Methoden umfassen die Bestimmung der Anzahl der notwendigen Schritte (oder der notwendigen Rechenzeit), die Untersuchung der Anzahl der notwendigen Speicherzellen und die Analyse des Verhaltens des Algorithmus in Bezug auf die Größe der Eingabe.

In diesem Kapitel werden wir uns mit verschiedenen Aspekten der Komplexitätstheorie beschäftigen.

Effizienzbestimmung von Algorithmen

Rechenzeit
belegter Speicher
Eingabe/Ausgabe (mit Wirkung auf Laufzeit)
Hauptspeicherzugriffe
Externer Speicher (um Faktor 100 langsamer)

Faktoren

Leistungsfähigkeit der Hardware
Qualität des vom Compiler generierten Codes
Eingabe (Anzahl der Eingabewerte n)
Zeitkomplexität des Algorithmus ⇒ Laufzeit als Funktion der Eingabegröße ausgedrückt: T(n)

Die Komplexität von Algorithmen beschreibt, wie schnell die Laufzeit oder der Speicherbedarf eines Algorithmus mit der Größe der Eingabe wächst. Es gibt verschiedene Möglichkeiten, die Komplexität von Algorithmen zu messen, wie zum Beispiel die Anzahl der ausgeführten Operationen oder die Anzahl der Zugriffe auf den Speicher. Ein wichtiger Bestandteil der Algorithmenanalyse ist die Bestimmung der Laufzeitkomplexität, die normalerweise in der asymptotischen Notation angegeben wird. Ein Beispiel für einen Algorithmus mit niedriger Komplexität ist eine lineare Suche, die in \( \mathcal{O}(n) \) Zeit abläuft, während ein Beispiel für einen Algorithmus mit hoher Komplexität eine sortierte Suche ist, die in \( \mathcal{O}(n \log{} n) \) Zeit abläuft. Es ist wichtig, die Komplexität von Algorithmen zu verstehen, um die Leistung von Programmen zu optimieren und die richtigen Algorithmen für bestimmte Aufgaben auszuwählen.

Komplexitätstheorie

Komplexitätstheorie befasst sich mit

Zeitkomplexität (Aufwand an Rechenzeit)
Speicherkomplexität (Aufwand an Speicherplatz)

Abstraktes Maschinenmodell zugrundeliegend

Turingmaschine, Random-Access-Machine
Elementaroperationen (z. B. Zuweisung, Vergleich, arithmetische Operationen, Array-Zugriff)
Nicht-elementare Operationen (z. B. Schleife, Prozeduraufruf)

Komplexitätsklasse und asymptotisches Verhalten

von abstrakter Eingabegrößen abhängig

Fälle

T_best
Bester Fall (best case)
T_worst
Schlimmster Fall (worst case)
T_avg
Durchschnittlicher Fall (average case)

In der Komplexitätstheorie beschreiben Bester Fall (best case), Durchschnittlicher Fall (average case) und Schlimmster Fall (worst case) die verschiedenen Szenarien, in denen ein Algorithmus aufgerufen werden kann.

Best case bezieht sich auf das Szenario, in dem der Algorithmus am schnellsten ausgeführt wird. Dies kann zum Beispiel der Fall sein, wenn die Eingabe bereits sortiert ist und der Algorithmus diese Eigenschaft nutzen kann.
Average case bezieht sich auf das durchschnittliche Szenario, in dem der Algorithmus aufgerufen wird. Dies kann sich auf die durchschnittliche Laufzeit des Algorithmus oder auf die durchschnittliche Anzahl von Schritten beziehen, die der Algorithmus benötigt, um zu einem Ergebnis zu gelangen.
Worst case bezieht sich auf das Szenario, in dem der Algorithmus am langsamsten ausgeführt wird. Dies kann zum Beispiel der Fall sein, wenn die Eingabe in der schlechtesten möglichen Reihenfolge vorliegt und der Algorithmus diese Eigenschaft nicht nutzen kann.

boolean search(int s, int[] data) {
    for (int i = 0; i < data.length; i++) {
        if (data[i] == s) {
            return true;
        }
    }
    return false;
}

T_best: c ist das erste Element
T_worst: c ist nicht im Array enthalten
T_avg: c ist mit einer gewissen Wahrscheinlichkeit im Array enthalten

Wachstum von Funktionen

Quelle: Markus Nebel Sebastian Wild: Entwurf und Analyse von Algorithmen, 2. Auflage

Konstanten

Verhalten bei großen n ist von Interesse
Terme mit niedrigem Grad fallen wenig ins Gewicht

⇒ Wir betrachten nur die Terme mit dem höchsten Grad

n	1	2	3	10	100	1000	10000
T₁	3	7	13	111	10101	1001001	100010001
T₂	1	4	9	100	10000	1000000	100000000

\[ \begin{align*} T_1(n) = n^2 + n + 1 \\ T_2(n) = n^2 \\ T_1 \approx T_2 \end{align*} \]

Effekt der Rechner-Performance

Effekt der Performance nimmt mit wachsender Zeitkomplexität ab
Bei z. B. 2ⁿ ist es unerheblich, ob der Rechner 1000 Mal schneller ist
\( 2^{100} \approx 2^{90} \)
Wichtig ist die Größenordnung der Zeitkomplexität
Wir suchen die obere Schranke der Zeitkomplexität für große n

In der asymptotischen Notation wird die Laufzeitkomplexität eines Algorithmus in Bezug auf die Größe der Eingabe angegeben.

O-Notation

O-Notation oder Landau-Notation beschreibt die obere Schranke der Laufzeitkomplexität für große n

Seien \( f: \mathbb{N} \rightarrow \mathbb{R} \) und \( g: \mathbb{N} \rightarrow \mathbb{R} \) Funktionen
\( \mathcal{O}(g) = \lbrace f| \exists\ n_0 \in \mathbb{N}, c \in \mathbb{R}, c > 0:\ \forall\ n \ge n_0: |f(n)| \le c\cdot|g(n)| \rbrace \)
\( \mathcal{O}(g) \) ist die Menge aller Funktionen \( f \), die höchstens so stark wachsen, wie \( g \)
Falls \( f \in \mathcal{O}(g) \), dann ist \( f \) durch \( g \) nach oben beschränkt

Rechenregeln in der O-Notation

\( \mathcal{O}(\log_a{n}) = \mathcal{O}(\log{n}) \)
\( \mathcal{O}(k \cdot g(n)) = \mathcal{O}(g(n)) \)
\( \mathcal{O}(n^k + n^{k-1} + ...) = \mathcal{O}(n^k) \)

Die Landau-Notation, auch als Big-O-Notation bekannt, ist eine Methode zur Schätzung der asymptotischen Laufzeitkomplexität von Algorithmen. Sie gibt an, wie schnell die Laufzeit oder der Speicherbedarf eines Algorithmus mit der Größe der Eingabe wächst, indem sie den dominanten Faktor des Wachstums beschreibt.

In der Landau-Notation wird die Laufzeitkomplexität eines Algorithmus durch eine Funktion von der Größe der Eingabe n beschrieben. Beispielsweise ist die Laufzeitkomplexität eines Algorithmus, der in einer Schleife n-mal ausgeführt wird, in \( \mathcal{O}(n) \).

Das \( \mathcal{O} \) steht hierbei für die Landau-Notation und gibt an, wie schnell die Laufzeit des Algorithmus mit der Größe der Eingabe (in der Regel durch die Variable n repräsentiert) wächst.

Es ist wichtig zu beachten, dass die Landau-Notation nur die Wachstumsrate beschreibt und nicht die tatsächliche Laufzeit. Ein Algorithmus mit \( \mathcal{O}(n) \) Laufzeitkomplexität kann bei kleinen Eingabegrößen schneller sein als ein Algorithmus mit \( \mathcal{O}(\log{} n) \) Laufzeitkomplexität, wenn der konstante Faktor des Algorithmus mit niedriger Komplexität höher ist.

Da die O-Notation die obere Schranke betrachtet, handelt es sich um eine Worst-Case-Abschätzung.

Sprechweise

Für einige Komplexitätsklassen haben sich feststehende Begriffe eingebürgert

\( \mathcal{O} \)	sprechweise
\( \mathcal{O}(1) \)	konstant
\( \mathcal{O}(\log{} n) \)	logarithmisch
\( \mathcal{O}(n) \)	linear
\( \mathcal{O}(n \log{} n) \)	n log n
\( \mathcal{O}(n^2) \)	quadratisch
\( \mathcal{O}(n^3) \)	kubisch
\( \mathcal{O}(n^k) \)	polynomiell
\( \mathcal{O}(2^n) \)	exponentiell

Beispiele für die Komplexität

Komplexität	Beispiel
\( f \in \mathcal{O}(1) \)	Feststellen, ob eine Binärzahl gerade ist
\( f \in \mathcal {O}(\log n) \)	Binäre Suche im sortierten Feld mit n Einträgen
\( f \in \mathcal {O}({\sqrt {n}}) \)	Anzahl der Divisionen des naiven Primzahltests
\( f \in \mathcal {O}(n) \)	Suche im unsortierten Feld mit n Einträgen (Bsp. Lineare Suche)
\( f \in \mathcal {O}(n\log n) \)	Vergleichbasierte Algorithmen zum Sortieren von n Zahlen, Mergesort, Heapsort
\( f \in \mathcal {O}(n^{2}) \)	Einfache Algorithmen zum Sortieren von n Zahlen, Selectionsort
\( f \in \mathcal {O}(n^{m}) \)	Einfache Algorithmen
\( f \in \mathcal {O}(2^{n}) \)	Erfüllbarkeitsproblem der Aussagenlogik (SAT) mittels erschöpfender Suche
\( f \in \mathcal {O}(n!) \)	Problem des Handlungsreisenden (mit erschöpfender Suche)

Lineare Suche: Ein Algorithmus, der durch eine Liste von Elementen iteriert, um ein bestimmtes Element zu finden. Dieser Algorithmus hat eine Laufzeitkomplexität von \( \mathcal{O}(n) \), da er durch die Liste geht und die Anzahl der Iterationen direkt proportional zur Größe der Eingabe (n) ist.
Binäre Suche: Ein Algorithmus, der in einer sortierten Liste von Elementen nach einem bestimmten Element sucht. Dieser Algorithmus hat eine Laufzeitkomplexität von \( \mathcal{O}(\log{} n) \), da er die Liste jedes Mal in der Hälfte teilt, wenn er das gesuchte Element nicht gefunden hat und da die Anzahl der Iterationen logarithmisch zur Größe der Eingabe (n) ist.
Bubble sort: Ein Algorithmus zum Sortieren von Elementen in einer Liste, indem er benachbarte Elemente vergleicht und vertauscht. Dieser Algorithmus hat eine Laufzeitkomplexität von \( \mathcal{O}(n^2) \), da er durch die Liste geht und für jeden Durchlauf eine Anzahl von Vergleichen und Austauschen proportional zur Größe der Eingabe (n) durchführt.
Quicksort: Ein Algorithmus zum Sortieren von Elementen in einer Liste, indem er ein Element als Pivot wählt und die Liste in Elemente kleiner und größer als das Pivot aufteilt, und diese Schritte rekursiv durchführt. Dieser Algorithmus hat eine Laufzeitkomplexität von \( \mathcal{O}(n \log{} n) \), da er durch die Liste geht und für jeden Durchlauf eine Anzahl von Vergleichen und Austauschen proportional zur Größe der Eingabe (n) durchführt und die Anzahl der Durchläufe logarithmisch zur Größe der Eingabe (n) ist.

Θ-Notation

Θ-Notation liefert die asymptotisch scharfe Schranke für einen Algorithmus

Seien \( f: \mathbb{N} \rightarrow \mathbb{R} \) und \( g: \mathbb{N} \rightarrow \mathbb{R} \) Funktionen
\( \Theta(g) = \lbrace f| \exists\ n_0 \in \mathbb{N}, \exists c_1, c_2 \in \mathbb{R}:\ \forall\ n \ge n_0: c_1 \cdot g(g) \le f(n) \le c_2 \cdot g(n) \rbrace \)
\( \Theta(g) \) ist die Menge aller Funktionen \( f \), die genauso stark wachsen, wie \( g \)

Die Θ-Notation wird in der Praxis selten verwendet

Die Theta-Notation (Θ-Notation) ist eine weitere Methode zur Beschreibung der Laufzeitkomplexität von Algorithmen. Sie gibt an, wie schnell die Laufzeit eines Algorithmus im Durchschnitt mit wachsendem Eingabegröße zunimmt.

Die Θ-Notation beschreibt die Schätzung der Laufzeitkomplexität eines Algorithmus durch eine obere und eine untere Schranke. Ein Algorithmus hat eine Laufzeit von Θ(f(n)), wenn es eine Konstante c₁ und c₂ und eine Eingabegröße n₀ gibt, sodass für alle Eingabegrößen n > n₀ gilt: \( c_1 \cdot f(n) \le \text{Laufzeit des Algorithmus} \le c_2 \cdot f(n) \)

Das bedeutet, dass die tatsächliche Laufzeit des Algorithmus im Durchschnitt von der angegebenen Funktion f(n) abhängt.

Die Theta-Notation ist also enger als die Big-O-Notation, die nur die obere Schranke der Laufzeit angibt. Sie ermöglicht es uns, die durchschnittliche Laufzeit eines Algorithmus genauer zu beschreiben.

Wie die Big-O-Notation gibt Theta-Notation auch keine Auskunft über die tatsächliche Laufzeit des Algorithmus. Es ist nur eine Schätzung der durchschnittlichen Laufzeitkomplexität.

Die Θ-Notation hat in der Praxis keine große Bedeutung, weil es sehr schwierig ist, die Funktion g(n) nur schwer finden lässt.