Zeitkomplexität

#Definition #IntroProg #Informatik #MINTgrün #Studium

Laufzeit

In a nutshell

Die Laufzeit eines Algorithmus gibt an, wie viel Zeit benötigt wird, um eine Eingabegröße zu verarbeiten, oft in Abhängigkeit von der Größe der Eingabe dargestellt. Sie dient dazu, die Effizienz und Skalierbarkeit von Algorithmen zu bewerten und zu vergleichen.

Problem bei Laufzeitanalyse ist, dass die tatsächliche Laufzeit von vielen Faktoren abhängt
- Hardware
- Software
- Rechnerarchitektur
- Übersetzer
- Implementierung
  -> Laufzeit soll unabhängig von Hard- und Software gelten. D.h. wird in der Regel auf der Basis der von Pseudocode gemacht
Maschinenmodell - uniform
- Eine Pseudocode-Instruktion braucht einen Zeitschritt
- Wird eine Instruktion r-mal aufgerufen, werden r Zeitschritte benötigt
- Die Zahlengröße spielt keine Rolle
- für Schleifen gibt es Regeln:
  1. Sequenz: max der Teile.
  2. Schleife: (max. Iterationszahl) × (Body‑Komplexität).
  3. Halbierung / Verdopplung: O(log N)
  4. Geschachtelt: Komplexitäten multiplizieren.
  5. Danach Konstanten streichen.
Um die Laufzeit zu analysieren, schauen wir uns die Größenordnung der Laufzeit an. Also das asymptotische Verhalten der Laufzeit als Funktion der Eingabegröße n
- Details werde ignoriert
- Dadurch erhält man Laufzeit- / Wachstumsklassen (logarithmisch, linear, quadratisch, exponentiell, etc.), in die man Algorithmen einordnet.
Laufzeit eines Algorithmus hängt ab von:
- Größe der Eingabe (Parameter n)
- Art der Eingabe
- Beobachtungen
  - insertion sort ist bei aufsteigend sortierten Eingaben schneller
  - insertion sort ist bei absteigend sortierten Eingaben langsam
Die Laufzeit lässt sich als Funktion T(n) darstellen. n ist die Eingabegröße. Ziel ist es die oberen Schranken (Garantien) zu finden
- Obere Schranken: $f mit f (n \geq T (n))$
- Untere Schranken: $f mit f (n) \leq T (n)$
Da je nach Rechenmodell, also welche Hard- und Software verwendet wird, die tatsächliche Laufzeit stark variieren kann, rechnet man in Schritten

Laufzeitanalyse Beispiel

In diesem Beispiel ist der Wert von sum Äquivalent zu der Anzahl an Schritten, die der Algorithmus durchläuft
Nach der Ausführung hat sum den Wert $n$

\begin{array}{ll} LineareMethode (n) & Zeit \\ 1. sum \leftarrow 0 & 1 \\ 2. for i \leftarrow 1 to n do & n + 1 \\ 3. sum \leftarrow sum + 1 & n \end{array}

Nach der Ausführung hat sum den Wert $n^{2}$

\begin{array}{ll} QuadratischeMethode (n) & Zeit \\ 1. sum \leftarrow 0 & 1 \\ 2. for i \leftarrow 1 to n do & n + 1 \\ 3. for j \leftarrow 1 to n do & n \times (n + 1) \\ 4. sum \leftarrow sum + 1 & n^{2} \end{array}

Nach der Ausführung hat sum den Wert $n^{3}$

\begin{array}{ll} KubischeMethode (n) & Zeit \\ 1. sum \leftarrow 0 & 1 \\ 2. for i \leftarrow 1 to n do & n + 1 \\ 3. for j \leftarrow 1 to n do & n \times (n + 1) \\ 4. for k \leftarrow 1 to n do & n^{2} \times (n + 1) \\ 5. sum \leftarrow sum + 1 & n^{3} \end{array}

Größenordnungen:

Wachstum	W-Ordnungen	N = 1000	10N	100N	1000N
konstant	1	1 Minute	1 Minute	1 Minute	1 Minute
logarithmisch	log N	1 Minute	1,3 Minuten	1,6 Minuten	2 Minuten
linear	N	1 Minute	10 Minuten	2 Stunden	1 Tag
leicht überlinear	N log N	1 Minute	13 Minuten	3 Stunden	1½ Tage
quadratisch	N²	1 Minute	2 Stunden	5 Tage	23 Wochen
kubisch	N³	1 Minute	1 Tag	2 Jahre	2000 Jahre
exponentiell	2^N	1 Minute	∞	∞	∞

Fallunterscheidung

wie oben steht kann die Laufzeit bei gleichem n stark variieren. Deshalb führt man Fallunterscheidungen durch

Worst-Case Analyse

Für jedes n definiere Laufzeit
T(n) = Maximum über alle Eingaben der Größe n
Garantie für jede Eingabe / „schlechtester Fall“
Üblich für Laufzeitanalyse
Beobachtung:
- Betrachte nun Algorithmus A mit Laufzeit 100n und Algorithmus B mit Laufzeit 5n²
  - Ist n klein, so ist Algorithmus B schneller
  - Ist n groß, so wird das Verhältnis Laufzeit B / Laufzeit A beliebig groß
  - Algorithmus B braucht also einen beliebigen Faktor mehr Laufzeit als A (wenn die Eingabe groß genug ist)

Average-Case Analyse

Für jedes n definiere Laufzeit
T(n) = Durchschnitt über alle Eingaben der Größe n
Hängt von Definition des Durchschnitts ab (wie sind die Eingaben verteilt)

Best-Case Analyse

Für jedes n definiere Laufzeit
T(n) = Minimum über alle Eingaben der Größe n
„Nicht“ garantiert für jede Eingabe / „bester Fall“

Beispiel: Laufzeitanalyse von insertion sort

\begin{array}{ll} InsertionSort (A) & Zeit \\ 1. for j \leftarrow 2 to length (A) do & n \\ 2. key \leftarrow A [j] & n - 1 \\ 3. i \leftarrow j - 1 & n - 1 \\ 4. while i > 0 and A [i] > key do & n - 1 + \sum t_{j} \\ 5. A [i + 1] \leftarrow A [i] & \sum t_{j} \\ 6. i \leftarrow i - 1 & \sum t_{j} \\ 7. A [i + 1] \leftarrow key & n - 1 \\ 5 n - 4 + 3 \sum t_{j} \end{array}

$t_{j}$ : Anzahl Wiederholungen der while-Schleife bei Laufindex j

Worst-Case

$t = j - 1$ für absteigend sortierte Eingabe

\begin{aligned} T (n) & = 5 n - 4 + 3 \cdot \sum_{j = 2}^{n} (j - 1) = 2 n - 4 + 3 \cdot \sum_{j = 1}^{n} j \\ = 2 n - 4 + 3 \cdot \frac{n (n + 1)}{2} = \frac{3 n^{2} + 7 n - 8}{2} \end{aligned}

-> konstante Faktoren wenig Aussagekräftig, da hier im Beispiel gezeigt wird, dass bei steigendem n alles von $3 n^{2}$ abhängt.

Asymptotische Laufzeitanalyse

ignorieren von konstanten Faktoren
Betrachte das Verhältnis von Laufzeiten für $n \to \infty$
Klassifiziere Laufzeiten durch Angabe von „einfachen Vergleichsfunktionen“

O-Notation – Obere Schranke

!250

$f (n)$ ist die tatsächliche Laufzeitfunktion, die alle Operationen und Konstanten beinhaltet.
$g (n)$ ist die Funktion, die wir zur Abschätzung des Wachstumsverhaltens verwenden.
$f (n) \in O (g (n))$ bedeutet, dass $f (n)$ für große $n$ nicht schneller wächst als $g (n)$ , abgesehen von Konstanten.

$Ω$ -Notation – Untere Schranke

!250

$f (n) \in Ω (g (n)) = {g (n) ∣ \exists c > 0, n_{0} > 0, so dass für alle n \geq n_{0} gilt: f (n) \geq c \cdot g (n)}$
$wobei f (n), g (n) > 0$
$f (n) \in Ω (g (n)$ bedeutet, dass $f (n)$ für $n \to \infty$ mindestens so stark wächst wie $g (n)$
Beim Wachstum ignorieren wir konstanten
$f (n) \in Ω (g (n)) ⟺ g (n) \in O (f (n))$

$Θ$ -Notation (Theta-Notation)

$f (n) \in Θ (g (n))$
Die Theta-Notation beschreibt, dass eine Funktion $f (n)$ sowohl asymptotisch nach oben als auch nach unten durch eine Funktion $g (n)$ beschränkt ist
$c_{1} \cdot g (n) \leq f (n) \leq c_{2} \cdot g (n) für alle n \geq n_{0}$ ,
- wobei:
  - $c_{1}$ und $c_{2}$ sind positive Konstanten.
  - $n_{0}$ ist eine Grenze, ab der diese Ungleichung gilt.

Echte obere und untere Schranke

o-Notation: echte obere Schranke
$ω$ -Notation: echte untere Schranke

Interpretation

"asymptotische Version"	von
O	$\leq$
$Ω$	$\geq$
$Θ$	$=$
o	$<$
$ω$	$>$

Ausdruck	Wachstum von $f$	Vergleich	Wachstum von $g$
$f \in o (g)$	Wachstum von $f$	$<$	Wachstum von $g$
$f \in O (g)$	Wachstum von $f$	$\leq$	Wachstum von $g$
$f \in Θ (g)$	Wachstum von $f$	$=$	Wachstum von $g$
$f \in Ω (g)$	Wachstum von $f$	$\geq$	Wachstum von $g$
$f \in ω (g)$	Wachstum von $f$	$>$	Wachstum von $g$

Mehrere Parameter & Datenstrukturen:

Graph‑Durchlauf: äußere Schleife über V Knoten, innere über ausgehende Kanten ⇒ $Θ (E)$ , weil jede Kante einmal.
- PriorityQueue.add(): $O (\log N)$ in Queue‑Größe ⇒ Algorithmus oft $O (E \log E)$ .
Amortisierte vs. Worst‑Case Kosten beachten.

Laufzeitklassen


$n!$	faktoriell
$O (2^{n})$	exponentiell
$O (n^{3})$	kubisch
$O (n^{2})$	quadratisch (polynomiell)
$O (n \log (n))$	super-linear
$O (n)$	linear
$O (\sqrt{(x)})$	Wurzelfunktion
$O (\log (n))$	logarithmisch
$O (1)$	beschränkt/konstant

Hierarchie

$O (\log n) \subseteq O (n) \subseteq O (n^{2}) \subseteq O (n^{c}) \subseteq O (2^{n})$
$(für c \geq 2)$ (nicht vollständig)
!Laufzeitklassen Vergleich.png

Laufzeitanalyse von Sortieralgorithmen

insertion sort
- Worst-Case: $O (n^{2})$
- Best-Case: $O (n)$
selection sort
- Worst Case: $O (n^{2})$
bubble sort
- Komplexität: $O (n^{2})$
count sort
- Komplexität: $O (n + m)$
  - n = Länge Array
  - m = Wertebereich

Laufzeit elementarer Java-Strukturen (worst-case)

Struktur	Operation	Laufzeit
Stack (Resizing‑Array)	push, pop	O(1)
Queue (Ring‑Array)	enqueue, dequeue	O(1)
LinkedList	addFirst, pollFirst	O(1)
	get(i), set(i), contains	O(N)
PriorityQueue (Heap)	add, removeMin	O(log N)
ArrayList / ArrayDeque	addLast	amort. O(1)

(ArrayDeque meist schnellste Deque; ArrayList Einfügen mittendrin O(N)).

Rekursionsbaum

Muster	Baumhöhe	Verzweigungen k	Gesamtlaufzeit
T(N)=T(N−1)+c	O(N)	1	Θ(N)
T(N)=T(N/2)+c	O(log N)	1	Θ(log N)
T(N)=T(N−1)+T(N−2)+T(N−3)+c	O(N)	3	O(3ᴺ)
T(N)=2·T(N/2)+c	O(log N)	2	Θ(N)

Komplexitätsklassen

Komplexitätsklassen sind Kategorien, die Berechnungsprobleme danach gruppieren, wie viel Rechenzeit ein Algorithmus im schlimmsten Fall benötigt, um sie zu lösen, abhängig von der Größe der Eingabe.

Klasse	Definition	Bedeutung
P	Probleme lösbar in polynomieller Zeit	„praktisch“ effizient
NP	Lösung prüfbar in polynomieller Zeit	enthält P
NP‑schwer	Jedes NP‑Problem polynomiell reduzierbar	mind. so schwer wie NP
NP‑vollständig	in NP und NP‑schwer	härteste NP‑Probleme

P =? NP offen (Millennium‑Problem, 1 Mio $).
Polynomzeit für ein einziges NP‑vollständiges Problem ⇒ P = NP.

Typische NP‑vollständige Probleme

Traveling‑Salesman (TSP): Finde in einem vollständigen, gewichteten Graphen einen Zyklus mit minimalem Gewicht, der jeden Knoten genau einmal enthält
Hamilton‑Pfad/‑Zyklus: Finde einen Pfad, der jeden Knoten eines gegebenen Graphen genau einmal besucht.
Max‑Cut: Bestimme in einem gewichteten Graphen einen Schnitt mit maximalem Gewicht.
0/1‑Rucksack, auch bei Beschränkung auf ganzzahlige Gewichte

\sum_{k = 0}^{n} \frac{1}{2^{k}} = \frac{1 - (1 / 2)^{n + 1}}{1 - \frac{1}{2}} = 2 (1 - \frac{1}{2^{n + 1}}) = 2 - \frac{1}{2^{n}} .