====== 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 ===== {{ .:pasted:20251212-064144.png?400}} 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 [[https://de.wikipedia.org/wiki/Landau-Symbole|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 ====