Laufzeitaufwand von Algorithmen

Einführungsbeispiel: Bubble sort

Im der folgenden Programmierbox finden Sie eine Implementierung des Bubblesort-Algorithmus und des Quicksort-Algorithmus. Wir interessieren uns dafür, wie ihr Laufzeitaufwand von der Länge des zu sortierenden Arrays abhängt.

a) Wie könnte man den Laufzeitaufwand messen (zwei Verfahren/Maße)?
b) Entwickeln Sie eine Testklasse, die mit beiden Messverfahren bei beiden Algorithmen für verschieden Lange zufällig befüllte Arrays den Laufzeitaufwand misst.
c) Stellen Sie mithilfe einer Tabellenkalkulation für beide Algorithmen den Laufzeitaufwand in Abhängigkeit von der Arraylänge als Graph dar.
d) Welchen funktionalen Zusammenhang vermuten Sie für Bubblesort/Quicksort?

Messverfahren

Oft ist der Laufzeitaufwand eines Algorithmus vom Umfang der zu bearbeitenden Daten (z.B. Länge des Arrays der Eingangsdaten), der Zielgenauigkeit (z.B. Anzahl der Dezimalstellen bei Berechnung der Quadratwurzel) oder einer anderen Größe abhängig. Es gibt zwei Arten, diesen Aufwand in Abhängigkeit dieser Größe zu messen:

Zeitmessung
Zählverfahren, z.B.
- Zählen zeitkritischer Anweisungen (z.B. Zählung, wie viele Vertauschungen bei Bubble Sort benötigt werden) oder
- Zählen der Aufrufe der Ausführung rekursiver Methoden

Optimal wäre es, das Laufzeitverhalten eines Algorithmus für zufällig verteilte Eingangsdaten mit mathematischen Mitteln herzuleiten. Dies geht über die Lernziele dieses Kurses hinaus. Für einfache Algorithmen lässt sich die korrekte Laufzeit aber oft mit einfachen Plausibilitätsbetrachtungen korrekt ermitteln.

Die Landau-Notation

Sei $f: n \mapsto f(n)$ eine Funktion, die den Laufzeitaufwand eines Algorithmus in Abhängigkeit von einem Parameter $n$ (z.B. Länge eines Arrays) beschreibt. Oft will man zum Ausdruck bringen, dass $f$ für große $n$ ähnlich wächst wie eine andere bekannte Funktion, z.B.

$f$ hat konstanten Laufzeitaufwand
$f$ wächst wie $log(n)$ (logarithmischer Laufzeitaufwand)
$f$ wächst wie $n$ (linearer Laufzeitaufwand)
$f$ wächst wie $n\cdot log(n)$ (linear-logarithmischer Laufzeitaufwand)
$f$ nimmt zu wie $n^2$ (quadratischer Laufzeitaufwand)
$f$ nimmt zu wie $e^n$ (exponentieller Laufzeitaufwand)

Man schreibt dann $f \in \mathcal{O}(log(n))$, $f \in \mathcal{O}(n)$ usw. . Diese Schreibweise nennt man Landau-Notation.
Wenn $f$ konstanten Laufzeitaufwand hat, schreibt man: $f \in \mathcal{O}(1)$

Die Mengen $\mathcal{O}(1),\ \mathcal{O}(log(n)),\ \mathcal{O}(n),\ \ldots$ nennt man Komplexitätsklassen.

Nur für Interessierte:

Die Landau-Notation kann man für den vorliegenden Kontext (Laufzeitaufwand von Algorithmen) folgendermaßen definieren:

Seien $f, g: [0;\ \infty] \rightarrow {\rm I\!R}$ zwei Funktionen, so gilt $$f \in \mathcal{O}(g) \Leftrightarrow \exists\ C > 0\ \wedge \exists\ n_0 > 0 \mathrm{\ sodass\ } \forall\ n \in [n_0;\infty[ \mathrm{\ gilt:\ } |f(n)| \le C\cdot|g(n)| $$

Dabei bedeutet das Zeichen $\exists$: "Es existiert ein …" und das Zeichen $\forall$: "Für alle…".

Sicher werden Sie bemerkt haben, dass gilt $$\mathcal{O}(1) \subset \mathcal{O}(log(n)) \subset \mathcal{O}(n) \subset \ldots$$ In der Praxis gibt man immer die Zuordnung zur niedrigsten Komplexitätsklasse an, der der Algorithmus angehört.

Beispiele

1. Zugriff auf ein Element in einem Array

Wir betrachten das Array

int[] zahlen = {1, 3, 4, 7, 10, -2};

Beim Zugriff auf ein Element des Arrays, z.B. zahlen[3] berechnet der Computer die Adresse des Elements, indem er zur Startadresse des Arrays das 3-fache der Länge eines int-Wertes (d.h. $3 \cdot 4$ Byte) hinzuaddiert und dann das entsprechende Element aus dem Speicher holt. In Assembler sieht es ungefähr so aus:

LOAD index            // hier: 3
MUL 4                 // jeder int-Wert ist 4 Byte lang
ADD startadresseDesArrays
MOV zwischenspeicher 
LOAD (zwischenspeicher)

Die Zeit, die nötig ist, um diese Anweisungen auszuführen, ist nicht vom Index (hier: 3) abhängig, d.h. der Zugriff aufs n-te Element eines Arrays hat konstanten Zeitbedarf und gehört daher zur Komplexitätsklasse $\mathcal{O}(1)$.

2. Suche nach einem Wert in einem unsortierten Array

Sei int[] zahlen ein unsortiertes Array von Zahlen, in dem ein Wert int wert gesucht werden soll.

a) Ergänzen Sie das Programm!
b) Wie hoch ist der Laufzeitbedarf in Abhängigkeit von der Länge des Arrays im besten/schlechtesten/mittleren Fall?
c) Geben Sie je ein Beispiel für die Belegung von zahlen und den gesuchten Wert im besten/schlechtesten Fall an.

Um die Wirkung des Laufzeitverhaltens eines Algorithmus abschätzen zu können, interessiert man sich oft für drei Fälle:

Best case (minimaler Laufzeitaufwand bei "optimaler" Datenkonstellation)
Average case (durchschnittlicher Laufzeitaufwand)
Worst case (maximaler Laufzeitaufwand bei "ungünstigster" Datenkonstellation)

3. Suche nach einem Wert in einem binären Suchbaum

Um die Wirkung des Laufzeitverhaltens eines Algorithmus abschätzen zu können, interessiert man sich oft für drei Fälle:

Best case (minimaler Laufzeitaufwand bei "optimaler" Datenkonstellation)
Average case (durchschnittlicher Laufzeitaufwand)
Worst case (maximaler Laufzeitaufwand bei "ungünstigster" Datenkonstellation)