Datenstrukturen & Algorithmen

Es findet ein grosses "Umherhüpfen" im Suchbaum statt. Dies kann je nach System sehr langsam werden, da das Zugreiffen auf nahe gelegene Speicheradressen billiger ist als der Zugriff auf entfernte. (Caching-Effekt)

Laufzeit: \(\mathcal{O(n*log(n))}\)

Achtung: Benötigt extra Speicherplatz von \(\mathcal{O(n)}\)

Auf dem Divide-And-Conquer-Prinzip

Laufzeit: Normalerweise/Durchschnittlich: \(\mathcal{O(n*log(n))}\)

Im schlechtesten Fall \(\mathcal{O(n^2)}\)(Tritt aber in der Praxis prakitsch nie ein-> Wenn der Pivot immer sehr schlecht ist. Es ist auch eine Möglichkeit 3 Elemente zu wählen und den Median dieser Elemente als Pivot zu nehmen.)

Bekanntlich nimmt ein Suchverfahren die beliebigen Werte \(a_1 a_2a_3....a_n\)  entgegen. Damit das Suchverfahren korrekt sein kann, muss es eine beliebige Permutation der Reihe ausspucken können. Es gibt daher n! mögliche Lösungen. 

Stellt man sich den Suchalgorithmus als Entscheidungsbaum vor, bei welchem man am Ende immer die Lösungspermutation kennen muss, so muss der Suchbaum n! Endknoten haben. Mittels Induktion kann bewiesen werden, dass der mittlere Suchweg \(log(n!)\) entspricht, was \(\in \Theta (n*log(n))\) ist. 

Beim Bucketsort werden die zu sortierenden Werte etwas näher betrachtet und auf "Eimer" verteilt. In einen Eimer kommen Zahlen mit passenden Eigenschaften, Beispielsweise diejenigen mit einem bestimmten 1000er Wert (4000, 4512, 4129 in den 4er Eimer, 8102 in den 8er Eimer usw.). Die Eimer werden dann mit einem simpleren Sortieralgorithmus sortiert und anschliessend wieder zusammengesetzt. 

Lineare Laufzeit, besonders hilfreich bei grossen Datenmengen. 

Beim Radix-Sort werden die Werte im Array jeweils Ziffer für Ziffer betrachtet und anschliessend auf 10 unterschiedliche Buckets verteilt. Wir beginnen mit der führenden Ziffer (09124 kommt in die 0;12913, 11291 in die 1 usw.). Wir sammeln die Zahlen in aufsteigender Reihenfolge wieder ein. Anschliessend wird nach der zweiten Zahl sortiert, wieder aufgesammelt usw. Solange, bis wir durch alle Ziffern durch sind.

Statt mit der führenden Ziffer kann man auch mit der letzten Ziffer beginnen. Sei m die Anzahl verschiedener Ziffern  (bei Zahlen 10), l die Anzahl Ziffern pro Wert und n die Anzahl Datensätze, so ist \(\mathcal{O((n+m)*l)}\)

Eine BEschreibung von Daten und den darauf anwendbaren Operationen (zB Einfügen, Löschen, Suchen). Die Implementierung eines abstraktesn Datentyps nennt man Datenstruktur. 

Die Effizienz sagt aus, wie es sich mit der Laufzeit einzelnder oder einer Folge von Operationen verhält. 

Als Array (Laufzeiten: Siehe Lernkarten zuvor...)

Lineare Liste (Laufzeiten: Linear)

Skip-Liste: (Liste die mittels zusätzlichen Zeigern das Suchen wie in einem Suchbaum ermöglicht. Löschen, Einfügen ist linear, suchen in log(n)). 

Suchbaum

-> Die Schlüssel im linken Teilbaum sind immer kleiner als die Wurzel

-> Die Schlüssel im rechten Teilbaum sind immer grösser als die Wurzel

Korrektheit kann mit einem rekursiven durchlaufen getestet werden (Traversierung)

Inorder-Traversierung: Der Suchbaum T wird von unten Links bis unten rechts der Reihe nach ausgegeben. Stimmt die dabei entstehende Reihenfolge ist der Suchbaum korrekt aufgebaut. (Siehe Bild)

Preorder-Traversierung: Ausgeben von Wurzel, preorder(T.links), preorder(T.rechts)

Postorder-Traversierung: Ausgeben von postorder(T.links), postorder(T.rechts), Wurzel

Worst-Case ist \(\mathcal{\Theta(n)}\) (Schlechter Pivot)

Im Durchschnitt ca. \(\Theta(log(n))\) Wuhu :)

Best Case: \(\Theta(log(n))\)

Worst Case: \(\Theta (n)\)

Mittel: \(\Theta(\sqrt{n})\)

Für jeden Knoten muss gelten, dass sich die Höhe des linken und des rechten Teilbaumes um höchstens 1 unterscheiden

\(mb(h) = F_{h+2} \approx 0,7*1.6^{h+2}\), wobei F die Fibonacci Zahlen darstellen (0, 1, 1, 2, 3, 5, 8, ...)

Herleitung: Jeder Baum hat immer genau ein Blatt mehr als innere Knoten. Ist mb die Midestblattzahl eines AVL-Baumes, dann ist mb(h) = mb(h-1) +mb(h-2).

Höhe: Nein! Denn formt man die oben genannte Formel um erhält man, dass \(h \leq 1,44*log(n)\), d.h eine Höhe, die "nur" um 44% grösser ist als die eines normalen Suchbaumes. (Das "nur" steht so in den Notizen... Finde 44% ja nicht sooo unerheblich... Aber eben. Konstante Faktoren sind in D&A egal... grml)

Wir merken uns zu jedem Knoten die aktuelle "Balance". Werde der Knoten k unter p eingefügt. Die Balance sagt aus, ob die beiden unteren Teilbäume (von p) jeweils gleich gross sind (0), der linke (-1) oder der rechte (1) grösser ist.

Falls: \(bal(p) = \pm1 \mapsto bal(p) =0\): Es muss nichts weiter unternommen werden. Die Höhe des Baums hat sich nicht geändert. 

Falls \(bal(p) = 0 \mapsto bal(p) =\pm1\): Die Höhe des Baums hat sich geändert. Entsprechend muss die Balance auch in allen Elternknoten von p angepasst werden. 

\(0 < \frac{1}{n} < 1 \)\(< log(log(log(n))) < log(log(n)) < \sqrt{log(n)} < log(n) < log^2(n) < log^3 (n) < \sqrt{n} < n < n*log(n) < n^2 < n^2 * log(n) < n^3 < 2^n < n * 2^n < 3^n < n! < n^n <^{2n} \)

\(f \in \Omega (g) \), Asymptotische untere Schranke

\(\Omega (g) :=\{f: \mathbb{N} \to \mathbb{R}^+| \exists c \in \mathbb{R}^+, n_0 \in \mathbb{N} \forall n \geq n_0: f(n) \geq c*g(n) \}\)

\(f \in \Theta (g)\) ist asymptotisch scharf, d.h\(f \in \mathcal{O}(g) \wedge g \in \mathcal{O}(f)\). Beide Funktionen wachsen gleich schnell

\(\Theta(g) := \{f: \mathbb{N} \to \mathbb{R}^+| \exists c \in \mathbb{R}^+, n_0 \in \mathbb{N} \forall n \geq n_0: c^{-1}*g(n) \leq f(n) \leq c*g(n) \}\)

*Korrektheit: Das Programm muss machen, was es soll

*Effizienz: Wie viel Platz (Speicher) und Zeit benötigt der Algorithmus

*Qualität der Lösung: Wie nahe kommen wir an das Optimum?

Es soll ein Teilstück eines Arrays gefunden werden, in welchem die Summe aller Einträge maximal ist. 

Beispielsweise hilfreich beim Aktienkurs: In welchem Zeitraum hat die Aktie am meisten Gewinn erbracht?

Laufzeit beträgt\(\mathcal{O(n^2)}\)

Grundprinzip: Das Problem wird rekursiv in kleinere Teilprobleme zerlegt, bis man es Problemlos lösen kann. Anschliessend wird aus den Teillösungen die Gesamtlösung rekonstruiert.

Eines der wichtigsten Prinzipien für effiziente Algorithmen. Wird u.a in der Sortierung, beim multiplizieren von grossen Zahlen und der diskreten Fourier-Transformation benutzt.

Laufzeit: \(\mathcal{O(n*log(n))}\)

Es existiert eine Lineare Lösung mit der Laufzeit \(\mathcal{O(n)}\)

Sei randmax das Maximale-Subarray, welches bei i-1 endet und 

Maximum das Maximum im Bereich 1,..., i-1. Dann ist der Algorithmus der linearen Lösung: 

Kann nicht besser als linear werden, da jedes Element mindestens einmal angeschaut werden muss. 

Nimmt man an, dass das nicht betrachtete Element in der Lösung ist, so habe es den Wert\(-\infty\) (Egal was man macht, es wird wahrscheinlich grössere Max.-Subarrays geben). Sei das Element nicht in der Lösung enthalten, so habe es den Wert \(\infty\). (D.h es sollte zwingend enthalten sein, um den Wert maximal zu machen. 

Suchalgorithmus für das Suchen in bereits sortierten Listen. Es muss \(A[1] \leq A[2] \leq ... \leq A[n]\)

Basiert auf dem Divide-And-Conquer prinzip. Schlüsselmenge muss begrenzt sein

Laufzeit: \(\mathcal{O(log(n))}\)

Geht nicht schneller als \(\mathcal{O(log(n))}\)

Denn: Stellt man sich ein Array als binären Suchbaum vor, so hat der Baum immer die Höhe (log(n)). Wenn unsere gesuchte Zahl nun im untersten Knoten liegt, müssen wir mindestens log(n) Knoten betrachten. Ergo kann unser Algorithmus nicht schneller sein

Die Interpolationssuche ist eine Abwandlung der binären Suche. Im Gegensatz zur binären Suche, die das Array in gleichmässige Teilintervalle zerlegt, versucht die Interpolationssuche eine "günstigere" Zerteilung zu finden- Etwa so wie ein Mensch ein Wörterbuch durchsucht. Bei der Suche nach dem Namen Sxxx, schlägt der Mensch das Buch nicht direkt in der Mitte auf, sondern ca. bei 2/3. 

Funktioniert nur gut, wenn die Einträge ca. gleichmässig verteilt sind.