Buffl uses cookies to provide you with a better experience. You can find more information in our privacy policy.
Komplexität O(1)
Inkrementieren eines Ints
Konstant
praxistauglich
Komplexität O(log n)
Wiederholtes Halbieren einer Datenmenge
Logarithmisch
Komplexität O(n)
Durchlaufen einer Datenmenge
Linear
Komplexität O(n log n)
Wiederholtes Halbieren einer Datenmenge und Durchlaufen der Hälfte
Komplexität O(n²)
2-fach verschachtelte Schleife
Quadratisch
bedingt praxistauglich
Komplexität O(n³)
3-fach verschachtelte Schleife
Kubisch
Komplexität O(n^k) für festes k
k-fach verschachtelte Schleife
Polynomiell
Komplexität O(2n^n)
Generieren aller Teilmengen einer Datenmenge
Exponentiell
nicht praxistauglich
Wichtige Eigenschaften Array
Die Größe eines Arrays ist fest und wird beim Erzeugen mittels createArray festgelegt.
Die Größe kann nicht mehr geändert werden.
Ein Array kann also nicht wachsen oder schrumpfen / nicht dynamisch
Eigenschaften Liste
Eine Liste speichert eine Sequenz von Elementen.
Die Reihenfolge der Elemente ist wichtig.
Elemente können mehrfach vorkommen.
Listen können wachsen oder schrumpfen, die Größe kann sich also dynamisch ändern.
Was macht emptyList()
emptyList() Erstellt eine neue, leere Liste
list.indexOf(elem)
list.indexOf(elem) -> index Liefert den index von elem, -1 fallselem nicht in der Liste enthalten ist.
Wie funktionrt ein dynamisches Array?
Freie Plätze im Array reserviert, diese werden beim hinzufügen aufgefüllt mit dem Element.
Wenn kein Platz mehr frei ist, wird ein neues Array doppelter Größe erstellt
Insert/remove in dynamische Arrays
Wenn noch Plätze frei, verschiebe alle Einträge ab dem insert index um eins nach hinten/vorne und speichere elem an dem index.
Wenn kein/genug Platz dann verdoppeln/halbieren und alles um eins verschieben wie oben.
Eigenschaften verkettete Liste
Jeder Listeneintrag speichert:
-data Nutzdaten
-first zeigt auf den ersten Eintrag, dieser ist NIL wenn die Liste leer ist
-next zeigt auf den nächsten Eintrag, wenn dieser ins nichts zeigt dann ist es auch NIL
Bubble Sort
Durchlaufe die Sequenz und tausche zwei benachbarte Elemente, wenn die Ordnung nicht stimmt.
Nach erstem Durchlauf ist das größte Element am Ende.
Wiederhole solange bis bei einem Durchlauf keineVertauschungen nötig sind.
Insertion Sort
Links den sortierten Bereich mit dem ersten Element erstellen dann von links nach rechts immer 1 Element in den sortierten Bereich einfügen und sortieren.
Selection Sort
Index j des kleinsten Elements bestimmen, dann das kleinste Element mit Index 0 tauschen
Index j des nächstkleineren Elements bestimmen, dann mit Index 1 tauschen usw….
Unterschied Selection Sort und Insertion Sort
Bei Insertion Sort: Elemente durchgehen und das Element an die richtige Stelle einfügen
Bei Selection Sort: Indexposition durchgehen und das passende Element einfügen
Quick Sort
Divide and Conquer:
Pivotelement p wählen, das Element ganz rechts
Sequenz in zwei Teile aufteilen.
Conquer:
Linker Teil: nur Elemente <= p
Rechter Teil: nur Elemente > p
—> Schritt wiederholen mit den einzelnen Sequenzen, stoppen wenn die Sequenzen nur aus einem Element bestehen
Combine:
Setze die sortierten Teile wieder zusammen
Binärbäume Eighenschaften
leere Bäume schreibt man als NIL
Die Teilbäume eines Knotens heißen Kinder.
Ein Knoten ist ein Elternknoten.
Der einzige Knoten ohne Elternknoten heisst Wurzel
Knoten ohne Kinder heisst Blatt
Innerer Knoten: ein Knoten, der kein Blatt ist
Die Höhe eines Baums ist die Länge des längsten Pfads von der Wurzel zu einem Blatt
Heaps und deren Heapbedingung
Heaps sind Binärbäume bei denen die Heapbedingung gilt:
—> Wert am Elternknoten >= Wert der Kinder
—> unterste Ebene muss immer von links aufgefüllt werden
Heaps als Sequenz
Wurzel hat immer Index 0
Für die restlichen Indexe i gilt:
—> Index linkes Kind: 2* i +1
—> Index rechtes Kind: 2* i +2
—> Index Elternknoten: ⌊ ⁄(𝑖 − 1) 2⌋
Mit Wurzel beginnen und dann von links nach rechts die Kinder und Kindeskinder usw auffüllen
Heap Sort
Heap als Sequenz/Array aufschreiben und/oder Sequenz als Baum zeichnen
Heapbedingungen sicherstellen, also Knoten immer größer als Kinder.
—> Ermittle den größten Wert von knoten und dessen Kinder. Falls dieser Wert im Knoten steht ist die Heapbedingung schon erfüllt.
—> Wenn der größte Wert im Kind steht, muss das jeweilige Kind mit dem Knoten getauscht werden. Dies macht man solange von oben nach unten bis überall die Heapbedingung erfüllt ist
Durch die Heapbedingung, steht der größte Wert jetzt in der Wurzel. Damit ist dies auch der größte Wert in der Sequenz.
—> Tausche den ersten Wert mit dem letzten.
—> dieser Schritt wiederholt sich bis alle Werte sortiert wurden
Versickern von getauschtem Wert
—> Vertausche den ersten und letzten Wert der Sequenz auch im Heap und lasse diesen Wert versickern, also verschwinden
—> der getauschte Wert steht jetzt in der Wurzel und muss erneut auf Heapbeding überprüft werden
2-Wege-Merge-Sort
Auf Papier:
Sequenz in 2 möglichst gleichgroße Teile teilen
Dann in möglichst 2er Paare aufteilen
Danach in einzelne Teile aufteilen
Jetzt nacheinander rekursiv wie zuvor zusammensetzen und dabei mit Merge Sort(Hilfsarray) sortieren
Was der Code macht:
Reines 2-Wege-Merge-Sort
Sequenz wird in einzelne Stücke geteilt 1-elementig
Verschmelze nacheinander die einzelnen Paare miteinander und sortiere dabei
—> erst 2x 1-elementig wird zu 2-elementig
—> 2x 2-elementig wird zu 4-elementig
usw…
Natürliches 2-Wege-Merge-Sort
Sequenz in mehrere Teilsequenzen teilen (3er Paare)
Verschmelzen wie bei 2-Wege-Mergesort
Radix-Exchange-Sort
Sequenz in Binärdarstellung:
Selection-Sort Laufzeit
Best: O(n²)
Average: O(n²)
Worst: O(n²)
Stabil: nein
Insitu: ja
Rekursiv: nein
Insertion-Sort Laufzeit
Best: O(n)
Stabil: ja
Bubble-Sort Laufzeit
Quick-Sort Laufzeit
Best: O(n log n)
Average: O(n log n)
Rekursiv: ja
Heap-Sort Laufzeit
Worst: O(n log n)
Merge-Sort Laufzeit
Best: O(n) —> natürliches Merge-Sort
Insitu: nein, O(n)
Radix-Exchange-Sort Laufzeit
Best: O(n*b)
Average: O(n*b)
Worst: O(n*b)
Sequentielle Suche
Durchlaufen aller Datensätze bis entweder der Schlüssel gefunden wurde oder nicht
DIe Daten müssen nicht sortiert sein
Daten müssen nur durchlaufen. kein Zugriff auf i-te Element
0
Binäre Suche
Bedingungen das es funktionert:
—> sortierte Sequenz
—> Größe des Suchbereichs bekannt
—> direkter Zugriff auf i-tes Element
Wenn Sequenz leer —> nicht möglich
Ansonsten mittleres Element m betrachten:
—> Wenn m > k = linke Hälfte rekursivv mit binärer Suche
—> Wenn m < k = rechte Hälfte rekursiv mit binärer Suche
—> Wenn m = k : Fertig
Exponentielle Suche
Benutzen wenn Größe des Suchbereichs unbekannt, Bereich muss sortiert sein.
Suchbereich bestimmen:
—> Mit index i=1 starten, dann Index jeweils verdoppeln
—> Solange bis k <= seq[i]
—> wenn Bereich bekannt, binäre Suche mit Intervall der letzten beiden indexe
Unterschiede Liste, Baum, Graph
Liste:
—> Jeder Knoten (außer der letzte)hat einen Nachfolger
Baum:
—> Jeder Knoten (außer Wurzel) hat einen Vorgänger
—> Ein Knoten kann mehrere Nachfolger haben
Graph:
Ein Knoten kann mehrere „Vorgänger“ haben, Zyklen sind möglich
Binärbäume
Ist entweder leer oder ein Knoten mit linkem, rechtem Teilbaum welche Schlüssel und Werte enthalten (ähnlich wie bei Heap)
Tiefe eines Knotens k: Länge des Pfads von der Wurzel bis k
Höhe eines Knotens k: Länge des längsten Pfads zueinem Blatt.
Eigenschaften von Knoten im Code
node.left liefert den linken Teilbaum.
node.right liefert den rechten Teilbaum.
node.key liefert den im Knoten gespeicherten Schlüssel
node.value liefert die im Knoten gespeicherten Daten.
node.parent liefert den Elterknoten.
Binäre Suchbäume Eigenschaften
Beliebige Daten können gespeichert werden, nicht nur Zahlen
Suchbaumeigenschaft: Für jeden Knoten k gilt:
—> Alle Schlüssel im linken Teilbaum sind kleiner als k.key(Wurzel)
—> Alle Schlüssel im rechten Teilbaum sind größer als k.key(Wurzel)
—> Regel gilt dann weiterhin für die jeweiligen Elternknoten und dessen Kinder
—> jeder Schlüssel kommt nur einmal vor
Lookup Suchbäume
lookup(node, key) -> value Gibt den unter dem Key gespeicherten Wert zurück.NIL falls nicht gefunden.
Wenn key < node.key, suche rekursiv in node.left.
Wenn key > node.key, suche rekursiv in node.right.
Ansonsten gib node.value zurück
Insert Suchbäume
insert(node, key, value) Fügt value unter dem gegeben Key in den Baum ein.
Falls node == NIL: erstelle neuen Knoten aus key und value und fertig.
Falls node.key == key: setze node.value = value und fertig.
Falls key < node.key: Füge in linken Teilbaum ein,also insert(node.left, key, value).
Dann fertig.
Ansonsten: Füge in rechten Teilbaum ein, also insert(node.right, key, value). Dann fertig.
Remove Suchbäume
Remove(node, key) Entfernt die unter dem Key gespeicherten Daten.
Falls node == NIL: fertig, key ist nicht im Baum.
Falls key < node.key: Lösche im linken Teilbaum, also remove(node.left, key). Dann fertig.
Falls key > node.key: Lösche im rechten Teilbaum,also remove(node.right, key). Dann fertig.
Ansonsten, also falls node.key == key: hier sind mehrere Fälle zu unterschieden, siehe Beispiel
Wenn node zwei Kinder hat muss man den symmetrischen Nchfolger entfernen:
Dies ist der Knoten mit dem kleinsten Wert, der größer als key ist (eins nach rechts, dann soweit links wie möglich)
Was sind vollständige Binärbäume
Alle Knoten haben 2 oder 0 Kinder
Alle Blätter haben dieselbe Tiefe
Was sind Degenerierte Binärbäume
Binärbäume die zu einer liste degenerieren
Durchlaufreihenfolge Suchbäume: Hauptreihenfolge (preorder)
Reihenfolge:
Besuche Wurzel
Durchlaufe linken Teilbaum
Durchlaufe rechten Teilbaum
Durchlaufreihenfolge Suchbäume: Nebenreihenfolge (postorder)
Durchlaufreihenfolge Suchbäume: Symmetrische reihenfolge (inorder)
—> gibt einen Suchbaum in geordneter Reihenfolge aus
Minimum und Maximum von Suchbäumen (Code)
maximum(node)
—> Falls node.right == NIL steht das Maximum in node.
—> Ansonsten: suche das Maximum in node.right§ „Soweit nach rechts wie möglich“
minimum(node)
—> Falls node.left == NIL steht das Minimum in node.
—> Ansonsten: suche das Minimum in node.left „Soweit nach links wie möglich“
Regeln Rot-Schwarz Bäume (Balncierte Suchbäume)
Jeder Knoten ist rot oder schwarz.
Die Wurzel des Baums ist schwarz.
Leere Teilbäume (NIL) sind schwarz.
Falls ein Knoten rot ist, sind beide Kinder schwarz.
Für jeden Knoten gilt: alle Pfade zu NIL enthalten dieselbe Anzahl schwarzer Knoten.
Einfügen von Knoten X in einen Rot-Schwarz Baum: X ist die Wurzel
Fall 1 X ist die Wurzel und ist Rot:
—> umfärben der Wurzel auf schwarz, fertig
Fall 2 X ist die Wurzel und ist schwarz:
—> kein umfärben nötig, da Bedingungen nicht verletzt
Einfügen von Knoten X in einen Rot-Schwarz Baum: Elternknoten von X ist schwarz
Keine Änderung nötig, da keine Bedingung verletzt wird
Einfügen von Knoten X in einen Rot-Schwarz Baum: Elternknoten von X ist rot, X ist linkes Kind und Onkel Y ist rot
Einfügen von Knoten X in einen Rot-Schwarz Baum: Elternknoten von X ist rot, X ist linkes Kind und Onkel Y ist schwarz
Einfügen von Knoten X in einen Rot-Schwarz Baum: Elternknoten von X ist rot, X ist rechtes Kind und Onkel Y ist rot
Einfügen von Knoten X in einen Rot-Schwarz Baum: Elternknoten von X ist rot, X ist rechtes Kind und Onkel Y ist schwarz
Rotieren bei Bäumen
Imperative Datenstrukturen - einfach verkette Liste
Zwischenversionen werden gelöscht
Liste wird durch Operationen destruktiv verändert
Funktionale Datenstrukturen
Funktionale Datenstrukturen sind unveränderbar
Änderungsoperationen liefern nur eine veränderte Kopie
—> Besser sind effiziente funktionale Datenstrukturen, diese vermeiden Kopien soweit möglich
—> Die ursprüngliche Datenstruktur bleibt unverändert erhalten
Vorteile Funktionale Datenstrukturen
Programme sind oft einfacher zu verstehen und zu warten.
In nebenläufigem Code sind unveränderbare Datenstrukturen einfacher zu verwenden.
Es gibt Algorithmen, die auch Zugriff auf alte Versionen einer Datenstruktur benötigen.
Was macht list.prepend?
prepend liefert eine Kopie der ursprünglichen Liste und erweitert diese um das gewünschte Element
—> Die ursprüngliche Liste bleibt unverändert, man kann auf die einzelnen Versionen zugreifen
Weiteres Beispiel:
Prepend schiebt die neue Liste vor die alte. Die neue Liste zeigt im next Attribut auf die bisherige Liste
—> list2(egg, bar) zeigt auf list1(foo) zeigt auf list0 (ursprüngliche Liste)
Was macht list.Empty ?
prüft ob Liste leer ist
—> prüfe first == NIL;
Was macht list.head?
liefert das vorderste Element der Liste
—> liefert String “egg”
Was macht list.tail ?
liefert alles aus der Liste außer das erste Element
Was macht list.reverse ?
reverse liefert eine umgedrehte Kopie von der Liste
—> Liste durchlaufen und diese in umgekehrter Reihenfolge aufbauen
Wie kann man eine funktionale Queue realisieren?
Mit zwei Listen:
front: Anfang der Queue, hier werden Elemente mittels dequeue entfernt.
back: Ende der Queue, hier werden neue Elemente mittels enqueue eingefügt.
funktionale Queue: Wie funktionieren front und back?
front: Anfang der Queue (ImmutableList)
—> Elemente werden mittels dequeue von vorne entfernt
—> der früheste Einfügezeitpunkt steht am Anfang der Liste
—> die Elemente werden nach ihrem Einfügezeitpunkt aufsteigend sortiert
back: Ende der Queue (ImmutableList)
—> Elemente werden mittels enqueue vorne eingefügt
—> Alle Elemente in back haben einen späteren Einfügezeitpunkt als die Elemente in front
—> der späteste Einfügezeitpunkt steht am Anfang der Liste
—> die Elemente werden nach ihrem Einfügezeitpunkt absteigend sortiert
weitere Regeln für front und back (Invariante):
—> front ist nur leer, falls back auch leer ist
—> Wenn front leer wird, wandern die Elemente von back in umgekehrter Reihenfolge nach front, da diese absteigend sortiert waren.
Was macht emptyQueue() ?
front und back werden auf eine leere funktionale Liste gesetzt
Was macht queue.isEmpty ?
Prüfe ob queue.front leer ist
—> Beachte: wenn queue.front leer ist muss wegen der Invariante auch queue.back leer sein.
Was macht queue.peek —> elem ?
Nimm das erste Element aus queue.front.
—> Beachte: falls es zu einem Fehler kommt, weil queue.front leer ist, ist das ok, denn dann ist die ganze Queue leer.
Was macht queue.enqueue(elem) ?
Fügt der Queue ein neues Element hinzu.
Normalfall: füge das neue Element mittels prepend in queue.back ein.
Spezialfall: Wenn queue.front leer ist, muss auch queue.back leer sein. Wir dürfen nicht in queue.back einfügen. Deshalb fügen wir mittels prepend in queue.front ein
Was macht queue.dequeue() —> elem ?
Liest und entfernt das erste Element der Queue (queue.front.head)
—> mittels queue.front.tail wird entfernt
Wenn queue.front leer ist/werden würde, umschichten:
—> queue.back umdrehen, da es absteigend sortiert war (front ist aufsteigend sortiert),
—> queue.back wird zur neuen leeren Liste und front enthält seine alten Elemente
Was sind Funktionale Arrays
Ein Array in Binärbaumdarstellung. Zugriff auf Elemente über Indexe in Bitrepresäntation
—> Ein Blatt des Baums enthält eine Referenz auf das Arrayelement,so dass der Pfad zum Blatt den Index angibt.
—> Innere Knoten enthalten keine Daten.
Funktionale Arrays - Verzweigungsgrad
Ein vollständig gefüllter Baum mit Verzweigungsgrad k und Höhe h hat k^h Blätter.
—> Also mit Höhe h maximal k^h Arrayelemente.
Wie funktionert Modulo %?
Modulo gibt den Rest an, der bei einer Division übrig bleibt:
Bsp. 25 mod 20 = 5
Bsp. 20 mod 25 = 20 weil nicht einmal teilbar, dann bleibt einfach die zahl vorne stehen als rest
Ausnahmen:
Wenn die erste Zahl minus ist:
—> Ausrechnen wie normal, Ergebnis wird einfach nur negativ. Bsp. -23mod20 = -3
Wenn die zweite Zahl minus ist:
—> gleiches Ergebnis wie sonst auch. Bsp. 23mod-20 = 3
Hashfunktion: Divisions-Rest-Methode
𝒉(k) = 𝒌 mod 𝒎 —> m ist gegeben; k ist der Schlüssel auch gegeben
Bsp: Berechnen Sie für folgende Schlüssel die Hashwerte: 0, -20, 519; mit m = 23
—> 0 mod 23 = 0
—> -20 mod 23 = -3
—> 519 mod 23 = 13
Hashfunktion: Multiplikative Methode
Last changeda year ago