Zusammenfassung teil1 Flashcards
Arrays und Listen vergleich;
Beliebiges Element suchen: Array Θ(n), List Θ(n)
Auf Element mit Index i zugreifen: Array Θ(1), List Θ(n)
Element am Anfang einfugen: Array Θ(n), List Θ(1)
Bubblesort
Laufzeit liegt im Worst- und Average-Case in Θ(n^2). Im
Best-Case kann die Laufzeit bei optimierten
Implementierungen in Θ(n) liegen.
Selectionsort:
(nicht stabil) Selectionsort sucht in jeder Iteration das kleinste
Element in der noch unsortierten Teilfolge, entnimmt es und fügt es dann an die sortierte Teilfolge an.
Laufzeit/Vergleiche: Die Laufzeit liegt immer (Best/Average/Worst-Case) in Θ(n^2).
Vertauschungen immer Θ(n)
Insertionsort:
(stabil) Insertionsort entnimmt der unsortierten Teilfolge ein Element und fugt es an richtiger Stelle in die (anfangs leere) sortierte Teilfolge ein.
Laufzeit/Vergleiche:
Best-Case Θ(n)
Worst-Case Θ(n^2).
Average-Case Θ(n^2)
Vertauschungen:
Best-Case Θ(n)
Worst-Case Θ(n^2).
Average-Case Θ(n^2)
Wann ist Algorithmus effizient?
Wir nennen einen Algorithmus effizient, wenn seine
Laufzeit polynomiell in der Eingabegröße ist.
Internes Sortieren:
bezeichnet Sortierverfahren die nur im Hauptspeicher arbeiten
Stabiles Sortieren:
Ordnungserhalten bei gleichen Schlüsseln. Das bedeutet bei gleichen Schlüsseln
bleibt die ürsprungsreihenfolge erhalten. Bspw. Radix-Sort
Merge Sort:
(stabil)
* Teile Array in zwei Hälften.
* Sortiere jede Hälfte rekursiv.
* Verschmelze zwei Hälften zu einem sortierten Ganzen.
Laufzeit/Vergleiche immer : Θ(n log n)
Vertauschungen immer: Θ(n log n)
Speicher: immer Θ(n)
Quick Sort:
(nicht stabil)
Quicksort: Benutzt auch das Divide-and-Conquer-Prinzip, aber auf
eine andere Art und Weise.
Teile: Wähle ”Pivotelement“ x aus Folge A, z.B. das an der letzten Stelle stehende Element.
Teile A ohne x so in zwei Teilfolgen A1 und A2, dass gilt: A1 enthält nur Elemente ≤ x. A2 enthält nur Elemente ≥ x. Herrsche: Rekursiver Aufruf für A1. Rekursiver Aufruf für A2.
Laufzeit/Vergleiche:
Best/AVG Θ(n log n)
Worst Θ(n^2)
Speicher:
Best/AVG Θ(log n)
Worst Θ(n)
Vertauschungen:
Best Θ(n)
Worst/AVG Θ(n log n)
Lineare Suche
Best Case : Θ(1)
naives, sequenzielles Durchsuchen der Liste.
Worst/AVG Case: Θ(n)
Binäre Suche
Suchen in sortierter Liste durch Halbierung des Suchintervalls
Best Case : Θ(1)
naives, sequenzielles Durchsuchen der Liste.
Worst/AVG Case: Θ(logn)
Einsatz von Sortierverfahren Merge und quicksort
Quicksort:
Wird sehr oft in allgemeinen Sortiersituationen bevorzugt.
Mergesort:
Mergesort wird hauptsächlich fur das Sortieren von Listen verwendet.
Wird auch fur das Sortieren von Dateien auf externen Speichermedien eingesetzt.
- Dabei wird aber eine iterative Version von Mergesort (Bottom-up-Mergesort) verwendet, bei der nur log n-mal eine
Datei sequentiell durchgegangen wird.
Handshaking lemma für ungerichtete Graphen
Summe (deg(v)) = 2*|E|
Adjazenzmatrix vs Adjazenyliste
Adjazenzmatrix:
Platzbedarf in Θ(n^2).
Uberprüfen, ob (u, v) eine Kante ist, hat Laufzeit : Θ(1).
Aufzählen aller Kanten hat eine Laufzeit von Θ(n^2)
Adjazenzliste:
Platzbedarf in Θ(m+n).
Uberprüfen, ob (u, v) eine Kante ist, hat Laufzeit : Θ(deg(u)).
Aufzählen aller Kanten hat eine Laufzeit von Θ(m+n)
Lichte und Dichte Graphen:
Graphen sind dicht (dense) falls m = Θ(n^2).
Graphen sind licht (sparse) falls m = O(n)
Fur dichte Graphen sind beide Darstellungsformen
(Adjazenzmatrix oder Adjazenzlisten) vergleichbar.
Lichte Graphen Adjazenzlisten
Breitensuche und Tiefensuche laufzeit
0(n+m)
Gerichteter azyklischer Graph Lemma
Lemma: G ist ein DAG genau dann wenn jeder Teilgraph von G eine Quelle hat.
Wir nennen eine Knoten v ohne eingehende Kanten in einem gerichteten Graphen (i.e. deg−(v) = 0) Quelle.
Topologische Sortierung Laufzeit:
O(n + m)
Min Heap Laufzeiten(analog für max)
Insert(H,v): O(log n).
FindMin(H): O(1)
Delete(H,i): O(logn)
ExtractMin(H): Kombination von FindMin und Delete unddaher in O(log n)
Dijkstra Laufzeit
Worst cases:
Liste O(n^2) Heap O((n + m) log n) FibHeap O(m + n log n)
m - Anzahl Kanten n - Anzahl Knoten
Interval Scheduling Laufzeit
Greedy: O(n*logn)
Kantenschnittlemma:
Sei S eine beliebige Teilmenge von Knoten
und sei e die minimal gewichtete Kante mit genau einem Endknoten in S. Dann enth¨alt der MST die Kante e.
Kreislemma:
Sei C ein beliebiger Kreis und sei f die maximal
gewichtete Kante in C. Dann enth¨alt der MST f nicht.
Kruskal vs Prim
Kruskal:
O(m logn)
Prim:
O(m logn) mit Priority Queue
O(m + nlogn) mit Fib Heap
Anwendung in der Praxis:
Fur dichte Graphen ( m = Θ(n^2)) ist Prims Algorithmus
besser geeignet. потому что в крускале нужно будет много вычеркивать ненужных что увеличивает лауфцайт
Fur dünne(lichte) Graphen ( m = Θ(n)) ist Kruskals Algorithmus
besser geeignet.
Inorder, PostOrder,Preorder
Inorder-Durchmusterung: Behandle rekursiv zunächst den linken
Unterbaum, dann die Wurzel, dann den rechten Unterbaum.
Preorder-Durchmusterung: Behandle rekursiv zunächst die Wurzel,
dann den linken Unterbaum, danach den rechten Unterbaum.
Postorder-Durchmusterung: Behandle rekursiv zunächst den linken
Unterbaum, dann den rechten Unterbaum, danach die Wurzel.
Successor und Predecessor
Successor: Nächster Knoten entsprechend der Inorder-Durchmusterungsreihenfolge oder null.
Predecessor: Vorhergehender Knoten entsprechend der Inorder-Durchmusterungsreihenfolge oder null.
AVL Baum laufzeit
Immer O(logn)
B baum der Ordnung m
- Alle Blätter haben gleiche Tiefe und sind leere Knoten.
- Jeder Knoten hat bis zu m Kinder.
- Jeder innere Knoten außer der Wurzel hat mindestens [m/2] Kinder. Die Wurzel hat mindestens 2 Kinder.
- Jeder Knoten mit l Schlussel hat l + 1 Kinder.
Lineares Sondieren
h(k, i) = (h’(k) + i) mod m
primären Häufung ist das Problem von liniares Sondieren
Quadratisches Sondieren:
h(k, i) = (h’(k) + c1i + c2i^2) mod m
die sekundären Häufungen ist das Problem von Quadratischen Sondieren
Double Hashing:
h(k, i) = (h1(k) + i*h2(k)) mod m.
Verbesserung nach brent
j1 = (j + h2(k)) mod m j2 = (j + h2(k')) mod m
Set:
Eine Collection, die keine duplizierten Elemente enth¨alt.
List:
Eine geordnete Collection (mit duplizierte Elementen).
Elemente können über einen Index angesprochen werden (nicht immer effizient)
Queue/Deque:
Verwalten von Warteschlangen.
FIFO, Priorit¨atswarteschlangen.
Einfugen und Löschen an beiden Enden bei Deque (“double ended queue”).
ArrayList vs Linked List
ArrayList:
*Indexzugriff auf Elemente ist uberall gleich schnell ( ¨O(1)).
*Einfugen und Löschen ist am Listenende schnell und wird mit wachsender
Entfernung vom Listenende langsamer (O(n)).
LinkedList:
*Indexzugriff auf Elemente ist an den Enden schnell und wird mit der Entfernung
von den Enden langsamer (O(n)).
*Einfugen und Löschen ohne Indexzugriff ist überall gleich schnell (O(1)).
PriorityQueue
Einfugen eines Elements und Löschen des ersten Elements in einer Queue der
Größe n sind in O(log n).
Löschen eines beliebigen Elements aus einer Queue der Größe n ist in O(n)
Lesen des ersten Elements in einer Queue ist in konstanter Zeit möglich (O(1)).
Ist als Min-Heap implementiert.
