Algorithmen: Suche und Komplexität

Suchen

• Sequentielle Suche: Prüft jedes Element einer Liste nacheinander, bis das gesuchte Element gefunden wird oder das Ende der Liste erreicht ist.
  • Effizienz: O(n) im schlechtesten Fall, da alle Elemente durchsucht werden müssen.
  • Vorteile: Einfach zu implementieren, effektiv für kleine Datenmengen.
  • Nachteile: Ineffizient für große Datenmengen.
• Binäre Suche: Effizient für sortierte Listen, vergleicht das gesuchte Element mit dem mittleren Wert der Liste.
  • Prinzip: Wenn das Element kleiner ist als der mittlere Wert, wird die rechte Hälfte ignoriert, wenn es größer ist, wird die linke Hälfte ignoriert. Dieser Prozess wird rekursiv wiederholt.
  • Effizienz: O(log n), da die Liste bei jedem Schritt halbiert wird.
  • Voraussetzung: Die Liste muss sortiert sein.

Komplexität

• Zeitkomplexität: Misst die Anzahl der Schritte, die ein Algorithmus in Abhängigkeit von der Eingabengröße benötigt.
  • Wichtige Notationen:
    • O(n): Linear (z.B. sequentielle Suche).
    • O(log n): Logarithmisch (z.B. binäre Suche).
    • O(n²): Quadratisch (z.B. Bubble Sort).
    • O(n log n): Log-linear (z.B. Mergesort, Quicksort).
• Raumkomplexität: Misst den Speicherplatz, den ein Algorithmus in Abhängigkeit von der Eingabengröße benötigt.
• Best-, Worst- und Average-Case: Beschreiben die minimalen, maximalen und durchschnittlichen Ressourcenanforderungen eines Algorithmus. Die Worst-Case-Analyse untersucht den ungünstigsten Fall.

Liste, Stack, Queue

• Liste: Eine Sammlung von Elementen in einer definierten Reihenfolge.
  • Lineare Struktur: Elemente sind nacheinander zugänglich.
  • Arten: Verkettete Listen (dynamische Speicherverwaltung) und Arrays (statischer Speicher).
• Stack: Datenstruktur, die dem Prinzip "Last In, First Out" (LIFO) folgt.
  • Operationen:
    • Push: Element wird oben auf den Stapel gelegt.
    • Pop: Element wird oben vom Stapel entfernt.
    • Peek: Das oberste Element wird betrachtet, ohne es zu entfernen.
  • Anwendungen: Rückverfolgung (z.B. bei rekursiven Aufrufen), Speicherverwaltung.
• Queue: Datenstruktur, die dem Prinzip "First In, First Out" (FIFO) folgt.
  • Operationen:
    • Enqueue: Einfügen eines Elements am Ende der Warteschlange.
    • Dequeue: Entfernen des ersten Elements.
  • Anwendungen: Warteschlangen in Betriebssystemen oder Netzwerken, Warteschlangen im Druckerspool.

Bäume

• Definition: Ein Baum ist eine hierarchische Datenstruktur mit einem Wurzelknoten und Kindknoten. Jeder Knoten (außer der Wurzel) hat genau einen Vorgänger.
• Binäre Suchbäume (BST): Ein binärer Baum, bei dem für jeden Knoten gilt:
  • Alle Knoten im linken Teilbaum sind kleiner.
  • Alle Knoten im rechten Teilbaum sind größer.
  • Effizienz der Operationen (Suchen, Einfügen, Löschen): O(log n) bei balancierten Bäumen, aber O(n) bei entarteten Bäumen (z.B. einer verketteten Liste).
• AVL-Bäume: Selbstbalancierender binärer Suchbaum, der dafür sorgt, dass die Baumhöhe O(log n) bleibt.
  • Balancierung: Bäume werden durch Rotationen balanciert, wenn die Balance um mehr als 1 abweicht.

Sortierverfahren

• Bubble Sort: Einfaches Sortierverfahren, bei dem benachbarte Elemente verglichen und getauscht werden, falls sie in falscher Reihenfolge stehen.
  • Komplexität: O(n²).
• Selection Sort: Findet in jedem Durchgang das kleinste Element und tauscht es an die richtige Stelle.
  • Komplexität: O(n²).
• Insertion Sort: Baut die Sortierung auf, indem Elemente in die bereits sortierte Liste eingefügt werden.
  • Komplexität: O(n²), aber bei fast sortierten Listen effizienter.
• Merge Sort: Teilt die Liste rekursiv, sortiert jede Hälfte und fügt sie wieder zusammen.
  • Komplexität: O(n log n).
  • Vorteile: Stabil und gut für große Datenmengen.
• Quick Sort: Wählt ein Pivot-Element, sortiert Elemente kleiner und größer als das Pivot und teilt die Liste rekursiv.
  • Komplexität: O(n log n) im Durchschnitt, aber O(n²) im schlechtesten Fall.

Selbstorganisierende Liste

• Eine dynamische Liste, die sich basierend auf der Häufigkeit oder Reihenfolge des Zugriffs reorganisiert.
• Ansätze:
  • Move-to-Front: Häufig verwendete Elemente werden an den Anfang verschoben.
  • Transpose: Häufig verwendete Elemente werden mit dem direkt davor stehenden Element getauscht.
  • Frequency Count: Elemente werden nach der Anzahl der Zugriffe sortiert.
• Vorteil: Schnellere Zugriffszeiten auf häufig verwendete Elemente, was bei Listen mit nicht gleichmäßigem Zugriffsmuster die Leistung verbessert.

Suchen (Sequentiell, Binär)

• Die sequentielle Suche prüft jedes Element einer Liste der Reihe nach, bis das gesuchte Element gefunden wird oder die Liste vollständig durchlaufen wurde.
• Die Effizienz der sequentiellen Suche beträgt im Worst-Case O(n), da alle Elemente überprüft werden müssen.
• Die sequentielle Suche ist einfach zu implementieren und für kleine Datenmengen effektiv.
• Die binäre Suche ist ein effizienter Algorithmus, der nur für sortierte Listen geeignet ist.
• Bei der binären Suche wird das gesuchte Element mit dem Mittelwert der Liste verglichen.
• Je nach Vergleichsergebnis wird die rechte oder linke Hälfte der Liste ignoriert, wodurch die Suche rekursiv fortgesetzt wird.
• Die Effizienz der binären Suche beträgt O(log n), da sich die Liste bei jedem Schritt halbiert.

Komplexität

• Die Zeitkomplexität beschreibt die Anzahl der Schritte, die ein Algorithmus benötigt, abhängig von der Größe der Eingabe (n).
• O(n) steht für eine lineare Komplexität, z. B. bei der sequentiellen Suche.
• O(log n) steht für eine logarithmische Komplexität, z. B. bei der binären Suche.
• O(n²) steht für eine quadratische Komplexität, z. B. bei Bubble Sort.
• O(n log n) steht für eine log-lineare Komplexität, z. B. bei Mergesort und Quicksort.
• Die Raumkomplexität gibt den benötigten Speicherplatz an, abhängig von der Größe der Eingabe.
• Die Worst-Case-Analyse untersucht den ungünstigsten Fall für den Algorithmus.

Liste, Stack, Queue

• Eine Liste ist eine Sammlung von Elementen in einer definierten Reihenfolge.
• Listen können als verkettete Listen (dynamisch) oder Arrays (statisch) implementiert werden.
• Ein Stack ist eine Datenstruktur nach dem LIFO-Prinzip (Last In, First Out).
• Die Operationen eines Stacks sind Push (Element hinzufügen), Pop (Element entfernen) und Peek (Betrachten des obersten Elements).
• Stacks werden für Rückverfolgungen, z. B. bei rekursiven Aufrufen, und für die Speicherverwaltung eingesetzt.
• Eine Queue ist eine Datenstruktur nach dem FIFO-Prinzip (First In, First Out).
• Die Operationen einer Queue sind Enqueue (Element hinzufügen), Dequeue (Element entfernen).
• Queues werden für Warteschlangen in Betriebssystemen, Netzwerken und Druckerspools verwendet.

Bäume

• Ein Baum ist eine hierarchische Datenstruktur mit einem Wurzelknoten und Kindknoten.
• Jeder Knoten hat genau einen Vorgänger, bis auf den Wurzelknoten.
• Ein binärer Suchbaum (BST) ist ein Baum, bei dem alle Knoten im linken Teilbaum kleiner und alle Knoten im rechten Teilbaum größer als der jeweilige Knoten sind.
• Die Effizienz von Suchen, Einfügen und Löschen in einem BST beträgt O(log n) bei balancierten Bäumen, aber O(n) bei entarteten Bäumen.
• AVL-Bäume sind selbstausgleichende binäre Suchbäume, bei denen die Baumhöhe O(log n) bleibt.
• Durch Rotationen werden AVL-Bäume ausbalanciert, wenn die Balance um mehr als 1 abweicht.

Sortierverfahren

• Bubble Sort ist ein einfaches Sortierverfahren, das benachbarte Elemente vergleicht und tauscht, falls sie in falscher Reihenfolge sind.
• Die Komplexität von Bubble Sort ist O(n²).
• Selection Sort findet in jedem Durchgang das kleinste Element und tauscht es an die richtige Stelle.
• Die Komplexität von Selection Sort ist ebenfalls O(n²).
• Insertion Sort fügt Elemente in eine bereits sortierte Liste ein und baut so die Sortierung auf.
• Die Komplexität von Insertion Sort ist O(n²) aber bei fast sortierten Listen effizienter.
• Merge Sort teilt die Liste rekursiv, sortiert die Hälften und fügt sie dann wieder zusammen.
• Die Komplexität von Merge Sort ist O(n log n).
• Merge Sort ist stabil und gut für große Datenmengen.
• Quicksort wählt ein Pivot-Element, sortiert Elemente kleiner und größer als das Pivot und teilt die Liste rekursiv.
• Die durchschnittliche Komplexität von Quicksort ist O(n log n), im Worst-Case jedoch O(n²).

Selbstorganisierende Liste

• Eine dynamische Liste, die sich anhand der Häufigkeit oder Reihenfolge des Zugriffs reorganisiert.
• Ansätze:
  • Move-to-Front: Häufig genutzte Elemente werden an den Anfang verschoben.
  • Transpose: Häufig genutzte Elemente werden mit dem davor stehenden Element getauscht.
  • Frequency Count: Elemente werden nach der Anzahl der Zugriffe sortiert.
• Vorteil: Schnellere Zugriffszeiten auf häufig genutzte Elemente, was die Performance bei Listen mit ungleichmäßigem Zugriff verbessert.

Suchen (Sequentiell, Binär)

• Die sequentielle Suche durchläuft jedes Element einer Liste der Reihe nach, bis das gesuchte Element gefunden wird oder das Ende der Liste erreicht ist. Die Effizienz ist im schlechtesten Fall O(n), da alle Elemente durchsucht werden müssen. Die sequentielle Suche ist einfach zu implementieren, aber für kleine Datenmengen am effektivsten.
• Die binäre Suche ist ein effizienter Algorithmus, der in einer sortierten Liste nach einem Element sucht. Die binäre Suche vergleicht das gesuchte Element mit dem mittleren Wert der Liste. Wenn das Element kleiner ist, wird die rechte Hälfte der Liste ignoriert, ist es größer, wird die linke Hälfte ignoriert. Dieser Prozess wird rekursiv wiederholt, bis das Element gefunden wird oder kein Element mehr übrig ist. Die Effizienz der binären Suche beträgt O(log n), da die Liste bei jedem Schritt halbiert wird. Voraussetzung ist, dass die Liste sortiert ist.

Komplexität

• Zeitkomplexität beschreibt die Anzahl der Schritte, die ein Algorithmus in Abhängigkeit von der Eingabengröße benötigt. Die wichtigsten Notationen sind:
  • O(n): Linear (z.B. sequentielle Suche)
  • O(log n): Logarithmisch (z.B. binäre Suche)
  • O(n²): Quadratisch (z.B. Bubble Sort)
  • O(n log n): Log-linear (z.B. Mergesort, Quicksort)
• Raumkomplexität beschreibt den Speicherplatz, den ein Algorithmus in Abhängigkeit der Eingabengröße benötigt.
• Best-, Worst- und Average-Case Analyse: Beschreiben die minimalen (best case), maximalen (worst case) und durchschnittlichen Ressourcenanforderungen eines Algorithmus.

Liste, Stack, Queue

• Eine Liste ist eine Sammlung von Elementen in einer definierten Reihenfolge. Sie ist eine lineare Datenstruktur, das bedeutet, dass die Elemente nacheinander zugänglich sind. Es gibt verkettete Listen, die dynamische Speicherverwaltung ermöglichen, und Arrays, die statischen Speicher verwenden.
• Ein Stack ist eine Datenstruktur, die nach dem Prinzip Last In, First Out (LIFO) arbeitet. Wichtige Operationen sind:
  • Push: Fügt ein Element oben auf den Stack.
  • Pop: Entfernt das Element oben vom Stack.
  • Peek: Gibt das oberste Element zurück, ohne es zu entfernen.
  • Anwendungsbeispiele: Rückverfolgung (z.B. in rekursiven Funktionen), Speicherverwaltung.
• Eine Queue ist eine Datenstruktur, die nach dem Prinzip First In, First Out (FIFO) arbeitet. Wichtige Operationen sind:
  • Enqueue: Fügt ein Element am Ende der Queue ein.
  • Dequeue: Entfernt das erste Element der Queue.
  • Anwendungsbeispiele: Warteschlangen in Betriebssystemen oder Netzwerken, Warteschlangen in Druckerspools.

Bäume

• Ein Baum ist eine hierarchische Datenstruktur. Er besteht aus einem Wurzelknoten und Kindknoten. Jeder Knoten (außer der Wurzel) hat genau einen Vorgänger und die Struktur verzweigt sich von oben nach unten.
• Ein binärer Suchbaum (BST) ist ein binärer Baum, in dem für jeden Knoten gilt:
  • Alle Knoten im linken Teilbaum sind kleiner als der Knoten.
  • Alle Knoten im rechten Teilbaum sind größer als der Knoten.
  • Die Effizienz der Operationen (suchen, einfügen, löschen) ist O(log n) bei balancierten Bäumen, aber O(n) bei entarteten Bäumen (z.B. eine verkettete Liste).
• Ein AVL-Baum ist ein selbstbalancierender binärer Suchbaum. Er sorgt dafür, dass die Baumhöhe O(log n) bleibt. Durch Rotationen werden Bäume balanciert, wenn die Balance um mehr als 1 abweicht.

Sortierverfahren

• Bubble Sort: Vergleicht benachbarte Elemente paarweise und tauscht sie, falls sie in falscher Reihenfolge sind. Komplexität: O(n²).
• Selection Sort: Findet in jedem Durchgang das kleinste Element und tauscht es mit dem Element an der aktuellen Position. Komplexität: O(n²).
• Insertion Sort: Fügt Elemente nacheinander in die bereits sortierte Liste ein. Komplexität: O(n²), aber bei fast sortierten Listen effizient.
• Merge Sort: Teilt die Liste rekursiv, sortiert die Hälften einzeln und führt sie dann zusammen . Komplexität: O(n log n). Vorteile: Stabil und gut für große Datenmengen.
• Quick Sort: Wählt ein Pivot-Element aus und sortiert die Elemente kleiner und größer als das Pivot. Die Liste wird dann rekursiv geteilt. Komplexität: O(n log n) im Durchschnitt, aber O(n²) im schlechtesten Fall.

Selbstorganisierende Liste

• Eine selbstorganisierende Liste ist eine dynamische Liste, die sich basierend auf der Häufigkeit oder Reihenfolge des Zugriffs reorganisiert.
• Ansätze:
  • Move-to-Front: Häufig verwendete Elemente werden an den Anfang der Liste verschoben.
  • Transpose: Häufig verwendete Elemente werden mit dem direkt davor stehenden Element getauscht.
  • Frequency Count: Elemente werden nach der Anzahl der Zugriffe sortiert.
• Vorteil: Schnellere Zugriffszeiten auf häufig verwendete Elemente. Dies verbessert die Leistung bei Listen mit ungleichmäßigem Zugriffsmuster.