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$ 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.