Informatik (Subject) / Sortieren und Suchen (Lesson)
There are 34 cards in this lesson
...
This lesson was created by jakobdanel.
This lesson is not released for learning.
- Quicksort - Hat D&C Ansatz - Sortiert nach einem Pivotelement und setzt dieses dann in die Mitte - Beim zusammneführen ist dann nichts mehr zu tun
- Quicksort Laufzeit Worst Theta(n²) Best Theta(n * lg n)
- Randomisierter Quicksort - Wählen eines zufälligen Pivotelements um einen Worst Case nahezu unmöglich zu machen
- Quick Sort Speicherbedarf in-situ
- Sortieren durch vergleichen - Sortieralgorithmus, welche auf paarweises Vergleichen und vertauschen von Elementen aufbaut
- Entscheidungsbaum - Binärbaum, welcher jede mögliche Permutation einer Liste enthält - Tiefe dieses Baumes entspricht dann der Worst Case Laufzeit eines Vergleichenden Sortieralgorithmus
- Tiefe des Entscheidungsbaums Die Tiefe eines Entscheidungsbaum muss h =Ω(n * lg n) sein
- Counting Sort - Arbeitet ohne Vergleichen - Zählt die Anzahl der Elemente mit einem Schlüssel - So können wir dann die Position dieser bestimmen
- Counting Sort Laufzeit T(n) = Theta (n +k)
- Counting Sort Speicherplatz T(n) = Theta(k)
- Stabiles Sortieren Ein Sortieralgorithmus ist stabil, wenn zwei Objekte mit gleichem Sortierschlüssel ihre Position nach durchlauf des Algorithmus nicht vertauscht haben
- Counting Sort Stabilität stabil
- Radix Sort - Die Stabilität eines Algorithmus ausnutzen um Laufzeit zu nutzen - Beispielsweise mit Counting Sort über jede Ziffer einer großen Zahl von hinten nach vorne iterieren
- Bucket Sort - Erweiterung auf reelle Zahlen des Radix Sort - Einteilen der Zahlen in Buckets, diese werden dann für sich sortiert - Annahme der Gleichverteilung der Werte
- Zeitkomplexität Erwartungswert Theta(n)
- Bucket Sort Speicheraufwand S(n) = Theta (n)
-
- Lineare Suche Über Array Iterieren um Objekt zu suchen (naive herangehensweise)
- Lineare Suche Laufzeit Theta(n)
- Binäre Suche Annahme: Eingabefolge ist sortiert Verfolgt Divide & Conquer Ansatz Vergleicht mittleres Element einer Teilliste mit dem zu suchenden und kann so den möglichen Speicherort finden
- Binäre Suche Laufzeit Theta(n * lg n)
- Untere Schranke für das Suchen Ω(n * lg n)
- Lineare Suche Speicherbedarf in-situ
- Binäre Suche Speicherbedarf in-situ
- Direkte Zugriffstabelle Zugriff auf ein objekt direkt über seinen Schlüssel
- Hashing Abbilden des zu speichernden Wertebereich, um Speicherplatz zu minimieren Zuordnung über eine Hashfunktion
- Kollision Zwei Schlüssel werden von der Hashfunktion auf die selbe Stelle in der Hashtabelle abgebildet
- Hashing - Divisionsmethode Nutzen einer modulo Funktion z.B.: h(k) = k mod m
- Hashing mit offener Adressierung Pro Hashtabellenplatz kann nur ein Objekt gespeichert werden Bei jedem neuen Eintrag wird geprüft ob Platz frei ist
- Insertion Sort Stabilität stabil
- Merge Sort Stabilität stabil
- Heap Sort Stabilität instabil
- Quicksort Stabilität instabil
-
- Radix Sort Stabiltät stabil
- Bucket Sort Stabilität stabil