Algorithmen und Datenstrukturen - Cheatsheet

Quick Sort

Definition:

Effizienter Vergleichssortieralgorithmus, der das Teile-und-Herrsche-Prinzip verwendet.

Details:

• Best- und durchschnittliche Komplexität: \(O(n \log n)\)
• Schlechteste Komplexität: \(O(n^2)\) (häufig durch schlechte Pivotauswahl)
• In-place, allerdings nicht stabil
• Wichtigste Schritte: Array um ein Pivot-Element aufteilen und rekursiv sortieren
• Pivotauswahl: z.B. erstes, letztes, mittleres Element oder zufällig
• Vorteile: schneller als andere Algorithmen mit gleichem Worst-Case (für große n mit gut gewähltem Pivot)
• Nachteile: anfällig für schlechten Pivot

Binäre Suche

Definition:

Ein Suchalgorithmus in sortierten Datenstrukturen. Teilt das Suchintervall wiederholt in zwei Hälften.

Details:

• Laufzeit: O(\log n)
• Voraussetzung: sortierte Liste
• Mittelwertindex: \(\text{mid} = \left\lfloor \frac{\text{low} + \text{high}}{2} \right\rfloor \)
• wenn \(\text{A[mid]} = \text{Schlüssel}\): Erfolg
• wenn \(\text{A[mid]} < \text{Schlüssel}\): Suche in rechter Hälfte
• wenn \(\text{A[mid]} > \text{Schlüssel}\): Suche in linker Hälfte

Graphen (gerichtet und ungerichtet)

Definition:

Graphen: Menge Knoten (bzw. Ecken) verbunden durch Kanten. Gerichtet: Kanten mit Richtung; ungerichtet: Kanten ohne Richtung.

Details:

• Knoten (\textit{V}): Menge von Knoten
• Kanten (\textit{E}): Menge von Kanten
• Gerichteter Graph: Kanten als (u,v)
• Ungerichteter Graph: Kanten als {u,v}
• Optimale Darstellung: Adjazenzmatrix oder Adjazenzliste
• Wichtige Algorithmen: DFS, BFS, Dijkstra, A*
• Komplexität häufig abhängig von Anzahl Knoten (|V|) und Kanten (|E|): \textit{O}(|E| + |V|)

AVL-Bäume

Definition:

Selbstbalancierender binärer Suchbaum, der die Höhenbalance für jede Teilbaum sicherstellt.

Details:

• Balance-Faktor: max. Unterschied der Höhen von linken und rechten Teilbaum = 1.
• Einfügen/Löschen: Rotation zum Ausbalancieren.
• Komplexität: O(log n) für Einfügen, Löschen, Suchen.
• Rotationen:
  • LL-Rotation
  • RR-Rotation
  • LR-Rotation
  • RL-Rotation

Algorithmische Komplexität und Effizienz (Landau-Notation)

Definition:

Algorithmische Komplexität beschreibt, wie sich der Ressourcenverbrauch eines Algorithmus (Zeit, Speicher) mit wachsender Eingabegröße verhält. Effizienz gibt an, wie gut ein Algorithmus diese Ressourcen nutzt. Landau-Notation wird verwendet, um dieses Verhalten mathematisch auszudrücken.

Details:

• Landau-Notation: Verwendet zur Beschreibung des asymptotischen Verhaltens eines Algorithmus.
• O(g(n)): Obergrenze der Wachstumsrate, worst-case Szenario.
• Ω(g(n)): Untergrenze der Wachstumsrate, best-case Szenario.
• Θ(g(n)): Genaues Maß der Wachstumsrate, falls obere und untere Schranke gleich sind.
• Beispiele:
  • Konstante Zeit: O(1)
  • Logarithmische Zeit: O(log n)
  • Lineare Zeit: O(n)
  • Quadratische Zeit: O(n^2)
  • Exponentialzeit: O(2^n)

Memoisierung

Definition:

Memoisierung speichert Ergebnisse bereits berechneter Funktionsaufrufe, um Wiederholungen zu vermeiden und die Performanz zu erhöhen.

Details:

• Reduziert doppelte Berechnungen in rekursiven Algorithmen.
• Nutzt Hash-Tabellen oder Arrays zur Speicherung.
• Besonders nützlich bei dynamischer Programmierung.
• Time Complexity: Ohne Memoisierung oft exponentiell, mit Memoisierung häufig polynomial.
• Speicherbedarf steigt durch Speichern der Zwischenresultate.
• z.B. Fibonacci-Berechnung: Rekursive Implementierung kann durch Memoisierung effizienter gestaltet werden.
• Pseudocode Beispiel:

  def fib(n, memo={}):    if n in memo:        return memo[n]    if n <= 2:        return 1    memo[n] = fib(n-1, memo) + fib(n-2, memo)    return memo[n]

Hash-basierte Suche

Definition:

Hash-basierte Suche verwendet Hash-Funktionen zur effizienten Zuordnung und Auffindung von Datenobjekten in einer Hash-Tabelle.

Details:

• Hash-Funktion: Eingabe auf eindeutigen Index im Array abbilden
• Konstante Zeitkomplexität im Durchschnitt: Durchschnittlich O(1) Zugriffszeit
• Kollisionen: Falls zwei Eingaben denselben Hashwert haben
• Umgang mit Kollisionen: Techniken wie Verkettung (Chaining) oder offenes Adressieren (Open Addressing)
• Wichtige Eigenschaften: Gute Hash-Funktion sollte gleichmäßige Verteilung der Hashwerte gewährleisten

Amortisierte Analyse

Definition:

Analyse der durchschnittlichen Laufzeit einer Operation in einer Sequenz von Operationen.

Details:

• Unterschied zu durchschnittlicher Laufzeitanalyse: berücksichtigt das schlimmste Szenario innerhalb einer Sequenz von Operationen
• Gesamtkosten über sämtliche Operationen teilen durch Anzahl der Operationen
• Methoden: Aggregierte Methode, Bankmethode, Potenzialmethode
• Beispiel: Operationen bei dynamischen Arrays (Arrayverdopplung)