Theorie

Inkrementieren eines Ints

Konstant

praxistauglich

Wiederholtes Halbieren einer Datenmenge

Logarithmisch

praxistauglich

Durchlaufen einer Datenmenge

Linear

praxistauglich

Wiederholtes Halbieren einer Datenmenge und Durchlaufen der Hälfte

praxistauglich

2-fach verschachtelte Schleife

Quadratisch

bedingt praxistauglich

3-fach verschachtelte Schleife

Kubisch

bedingt praxistauglich

k-fach verschachtelte Schleife

Polynomiell

bedingt praxistauglich

Generieren aller Teilmengen einer Datenmenge

Exponentiell

nicht praxistauglich

• 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

• 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.

emptyList() Erstellt eine neue, leere Liste

list.indexOf(elem) -> index Liefert den index von elem, -1 fallselem nicht in der Liste enthalten ist.

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

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.

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

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.

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.

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….

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

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

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 sind Binärbäume bei denen die Heapbedingung gilt:

—> Wert am Elternknoten >= Wert der Kinder

—> unterste Ebene muss immer von links aufgefüllt werden

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

1. Heap als Sequenz/Array aufschreiben und/oder Sequenz als Baum zeichnen

2. 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

   

3. 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

   

4. 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

   

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:

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…

Sequenz in mehrere Teilsequenzen teilen (3er Paare)

Verschmelzen wie bei 2-Wege-Mergesort

Sequenz in Binärdarstellung:

Best: O(n²)

Average: O(n²)

Worst: O(n²)

Stabil: nein

Insitu: ja

Rekursiv: nein

Best: O(n)

Average: O(n²)

Worst: O(n²)

Stabil: ja

Insitu: ja

Rekursiv: nein

Best: O(n)

Average: O(n²)

Worst: O(n²)

Stabil: ja

Insitu: ja

Rekursiv: nein

Best: O(n log n)

Average: O(n log n)

Worst: O(n²)

Stabil: nein

Insitu: ja

Rekursiv: ja

Best: O(n log n)

Average: O(n log n)

Worst: O(n log n)

Stabil: nein

Insitu: ja

Rekursiv: nein

Best: O(n) —> natürliches Merge-Sort

Average: O(n log n)

Worst: O(n log n)

Stabil: ja

Insitu: nein, O(n)

Rekursiv: ja

Best: O(n*b)

Average: O(n*b)

Worst: O(n*b)

Stabil: nein

Insitu: ja

Rekursiv: ja

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

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

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

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

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.

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.

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(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(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(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)

Alle Knoten haben 2 oder 0 Kinder

Alle Blätter haben dieselbe Tiefe

Binärbäume die zu einer liste degenerieren

Reihenfolge:

1. Besuche Wurzel

2. Durchlaufe linken Teilbaum

3. Durchlaufe rechten Teilbaum

Reihenfolge:

1. Durchlaufe linken Teilbaum

2. Durchlaufe rechten Teilbaum

3. Besuche Wurzel

Reihenfolge:

1. Durchlaufe linken Teilbaum

2. Besuche Wurzel

3. Durchlaufe rechten Teilbaum

   —> gibt einen Suchbaum in geordneter Reihenfolge aus

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“

1. Jeder Knoten ist rot oder schwarz.

2. Die Wurzel des Baums ist schwarz.

3. Leere Teilbäume (NIL) sind schwarz.

4. Falls ein Knoten rot ist, sind beide Kinder schwarz.

5. Für jeden Knoten gilt: alle Pfade zu NIL enthalten dieselbe Anzahl schwarzer Knoten.

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

Keine Änderung nötig, da keine Bedingung verletzt wird

Zwischenversionen werden gelöscht

Liste wird durch Operationen destruktiv verändert

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

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.

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)

prüft ob Liste leer ist

—> prüfe first == NIL;

liefert das vorderste Element der Liste

—> liefert String “egg”

liefert alles aus der Liste außer das erste Element

reverse liefert eine umgedrehte Kopie von der Liste

—> Liste durchlaufen und diese in umgekehrter Reihenfolge aufbauen

Mit zwei Listen:

1. front: Anfang der Queue, hier werden Elemente mittels dequeue entfernt.

2. back: Ende der Queue, hier werden neue Elemente mittels enqueue eingefügt.

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.

front und back werden auf eine leere funktionale Liste gesetzt

Prüfe ob queue.front leer ist

—> Beachte: wenn queue.front leer ist muss wegen der Invariante auch queue.back leer sein.

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.

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

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

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.

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.

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:

1. Wenn die erste Zahl minus ist:

   —> Ausrechnen wie normal, Ergebnis wird einfach nur negativ. Bsp. -23mod20 = -3

2. Wenn die zweite Zahl minus ist:

   —> gleiches Ergebnis wie sonst auch. Bsp. 23mod-20 = 3

𝒉(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