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.

Zur Erinnerung sehen Sie im Bild rechts die Graphen der obigen Funktionen. Natürlich interessieren wir uns in diesem Kontext nur für ihr Wachstum für große $n$, also nur für den 1. Quadranten!

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 balancierten binären Suchbaum

Da für Höhe $h$ eines balancierten binären Suchbaums mit $n$ Elementen gilt $h = log_2 (n + 1)$ (aufgerundet), und maximal $h$ Vergleiche nötig sind, um einen Wert in einem solchen Baum zu suchen, gehört die maximale Laufzeit (d.h. worst case) der Suche in einem balancierten Suchbaum zur Komplexitätsklasse $\mathcal{O}(log(n))$.

Man kann zeigen, dass auch die durchschnittliche Laufzeit (d.h. average case) in einem solchen Baum zur Komplexitätsklasse $\mathcal{O}(log(n))$ gehört.

Bemerkung:
Wegen $$log_a\ x = \frac{log_c\ x}{log_c\ a} = \frac{1}{log_c\ a}\cdot log_c\ x$$ unterscheiden sich die Funktionen $f(x) = log_a\ x$ und $g(x) = log_c\ x$ nur um eine Konstante, daher ist bei der Angabe der Komplexitätsklasse irrelevant, welche Basis der Logarithmus hat.

4. Bubble Sort, Quicksort

Zu Bubble Sort:
Bei einem Array der Länge $n$ wird die innere Wiederholung (for(int i = 0; i < = maxIndex; i++)) im Mittel $n/2$-mal durchlaufen. Man kann zeigen, dass im Mittel auch die Anzahl an äußeren Wiederholungen proportional zu $n$ ist, daher ist die mittlere Laufzeit (d.h. average case) von der Komplexitätsklasse $\mathcal{O}(n^2)$.

Quicksort:
Man nimmt vereinfachend an, dass das Array bei jeder Unterteilung (d.h. bei jedem rekursiven Aufruf der Methode sort) halbiert wird, d.h. bei $n$ Elementen gibt es $log_2\ n$ (aufgerundet) Unterteilungen. Die kleinen Teil-Arrays, die auf jeder "Ebene" der Unterteilungen in der Methode partition geordnet werden müssen, haben für jede Ebene zusammengenommen $n$ Elemente, daher ist der Ordnungsaufwand je Unterteilung proportional zu $n$. Insgesamt ist die mittlere Laufzeit (d.h. average case) daher von der Komplexitätsklasse $\mathcal{O}(n\cdot log\ n)$.

Bemerkung: Obige Argumentationen sind nicht streng mathematisch, sondern dienen nur zur Veranschaulichung.

Brute Force-Verfahren

Löst man ein Problem, indem man alle Möglichkeiten durchprobiert, so spricht man von einer brute force-Strategie.

Beispiele:

Zum Finden eines Passworts der Länge $n$ bei einem Alphabet der Länge $k$ sind im Mittel $\frac{k^n}{2}$ Versuche nötig.
Lösen eines Problems durch reines Backtracking
Wörterbuchangriff auf einen Passwortspeicher, in dem sich die salted hashes der Passwörter befinden.

In letzterem Fall ist es wichtig, eine Hashfunktion zu verwenden, deren Berechnung möglichst viel Laufzeitaufwand verursacht. Hoher Laufzeitaufwand kann also manchmal auch erwünscht sein!