====== 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**. 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 [[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 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 [[https://www.learnj.de/11/doku.php?id=hash:start#anwendungspeichern_von_passwoertern_als_salted_hash|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!