Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Komplexität

Einführung Komplexität

Auf dieser Seite wird das Thema Komplexität behandelt. Gegeben ist ein zu lösendes Problem. Es ist wünschenswert, dass der Algorithmus zur Berechnung der Lösung einen möglichst geringen Aufwand hat. Daher wird der Aufwand des Algorithmus (Komplexität) abgeschätzt . Zur Lösung von Problemen einer bestimmten Klasse gibt es einen Mindestaufwand.

Motivierendes Beispiel

Als Beispiel nutzen wir die sequentielle Suche in Folgen. Gegeben ist die Zahl b und n Zahlen, z.B. mit A[0...n-1] mit n>0, wobei die Zahlen verschieden sind. Gesucht ist ein Index $i\in \{0,...,n-1\}~mit~b=A[i]$, falls der Index existiert, sonst ist i = n. Die Lösung für das Problem ist:

i = 0; 
  while (i < n  &&  b != A[i]) 
    i++;

Der Aufwand der Suche hängt nun von der Eingabe ab, d.h vom gewählten Wert n, den Zahlen A[0],...,A[n] und von b. Es gibt zwei Möglichkeiten, eine erfolgreiche oder eine erfolglose Suche. Eine erfolgreiche Suche haben wir, wenn b=A[i] dann ist S=i+1 Schritte. Ist die Suche jedoch erfolglos, dann ist S=n+1 Schritte. Das Problem ist, dass die Aussage von zu vielen Parametern abhängt und unser Ziel ist eine globale Aussage zu finden, die nur von einer einfachen Größe abhängt, z.B. der Länge n der Folge.

Analyse erfolgreiche Suche

Im schlechtesten Fall wird b erst im letzten Schritt gefunden, d.h. b=A[n-1]. Dann wäre S=n. Im Mittel wird die Anwendung mit verschiedenen Eingaben wiederholt. Wenn man beobachtet wie oft b an erster, zweiter,..., letzter Stelle gefunden wird, hat man eine Annahme über die Häufigkeit. Läuft der Algorithmus k mal (k>1), so wird b gleich oft an erster, zweiter,....,letzter Stelle gefunden und somit k/n mal an jeder Stelle. Die Anzahl der Schritte insgesamt für k Suchvorgänge lässt sich folgendermaßen berechnen:

$M={\frac {k}{n}}\cdot 1+{\frac {k}{n}}\cdot 2+...+{\frac {k}{n}}\cdot n$

$={\frac {k}{n}}\cdot (1+2+...+n)$

$={\frac {k}{n}}\cdot {\frac {n\cdot (n+1)}{2}}$

$=k\cdot {\frac {n+1}{2}}$

Für eine Suche benötigt man $S={\frac {M}{k}}$ Schritte Daraus folgt, dass im Mittel ( bei einer Gleichverteilung) $S={\frac {n+1}{2}}$

Asymptotische Analyse

Zur Analyse der Komplexität geben wir eine Funktion als Maß für den Aufwand an. $f:\mathbb {N} \to \mathbb {N}$. Das bedeutet f(n)=a bei Problemen der Größe n beträgt der Aufwand a. Die Problemgröße ist der Umfang der Eingabe, wie z.B. die Anzahl der zu sortierenden oder zu durchsuchenden Elemente. Der Aufwand ist die Rechenzeit( Abschätzung der Anzahl der Operationen, wie z.B. Vergleiche) und der Speicherplatz.

Aufwand für Schleifen

Wie oft wird die Wertezuweisung x=x+1 in folgenden Anweisungen ausgeführt?

 x = x +1

1-mal

  for (i = 1; i <= n; i++)   
    x = x + 1;

n-mal

  for (i = 1; i <= n; i++)
   for (j = 1; j <= n; j++) 
         x = x + 1;

$n^{2}$-mal

Aufwandsfunktion

Die Aufwandsfunktion $f:\mathbb {N} \to \mathbb {N}$ ist meist nicht exakt bestimmbar. Daher wird der Aufwand im schlechtesten Fall und im mittleren Fall abgeschätzt und die Größenordnung ungefähr errechnet.

Vergleich Größenordnung

Funktion	n=100	n=10.000	n=100.000
log n	4,6	9,2	11,5
$n^{2}$	10.000	100.000.000	10.000.000.000
$n^{3}$	1.000.000	$10^{12}$	$10^{15}$

Problemstellung

Wie können wir das Wachstum von Funktionen abschätzen und wie verhalten sich die Funktionen zueinander? Das Ziel ist, die Funktion $t_{i}(n)$ zu wählen, die $f(n)$ nach oben beschränkt.

$f(n)={\frac {1}{3}}~n^{2}$

$t_{1}(n)={\frac {1}{4}}~n^{2}$

$t_{2}(n)=n$

$t_{3}(n)={\frac {1}{3}}~n^{2}+2$

$t_{4}(n)=2^{n}$

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 7.3 zu finden.