Die Folien sind teilweise inspiriert von oder basierend auf Lehrmaterial von Prof. Dr. Ritterbusch.
https://delors.github.io/theo-algo-suchen_auf_arrays/folien.de.md.html
https://delors.github.io/theo-algo-suchen_auf_arrays/folien.de.md.html.pdf
Bei der Erstellung der Unterlagen wurden KI Assistenten (insbesondere Claude aber ggf. auch ChatGPT, Ollama mit Gemma/LLama/Qwen oder OpenCode mit Kimi/Qwen/Deepseek...) unterstützend eingesetzt. Dies erfolgte insbesondere zur Unterstützung bei der Generierung von Grafiken (d. h. SVG Dateien), oder um sich Übersichtstabellen generieren zu lassen. Weiterhin wurde KI zur allgemeinen Qualitätssicherung eingesetzt. Inhalte, die ggf. von der KI vorgeschlagen wurden, wurden im Falle der Übernahme explizit validiert und angepasst.
Welche Skalierung haben gesuchte Daten sind im Array?
Nur Vergleich auf Gleichheit, keine natürliche Ordnung oder Zahlbegriff.
Ein Beispiel für eine nominal skalierte Datenmenge wäre die Menge der Farben. Es gibt keine natürliche Ordnung der Farben, und es gibt auch keinen natürlichen Zahlenbegriff, der die Farben beschreibt. Ein weiteres Beispiel ist eine Liste von Wohnorten.
Es gibt Größenvergleiche und damit eine Sortierung, aber kein Zahlbegriff.
Ein Beispiel für eine ordinale skalierte Datenmenge wäre die Menge der Kleidergrößen (S,M,L,XL,...). Es gibt eine natürliche Ordnung der Kleidergrößen, aber es gibt keinen natürlichen Zahlenbegriff, der die Kleidergrößen beschreibt. Ein weiteres Beispiel ist die Bewertung von Filmen auf einer Skala von 1 bis 5 Sternen.
Es gibt Größenvergleiche und Zahlbegriff.
1// A 1-indiziertes Array, das durchsucht wird2// n Größe des Arrays3// needle der zu suchende Wert4function LinearSearch(A,n,needle)5for i := 1,...,n do6if A[i] == needle then7return i8return nil
Laufzeit und Elementzugriffe kann asymptotisch durch abgeschätzt werden.
1// A aufsteigend sortiertes Array, das durchsucht wird2// l untere Grenze (Index im Array)3// u obere Grenze (Index im Array: untere Grenze <= obere Grenze)4// needle der zu suchende Wert5function BinarySearch(A,l,u,needle)6upper := u7lower := l8repeat9pos := floor((upper + lower) / 2)10value := A[pos]11if value == needle then return pos12else if value > needle then13upper := pos − 114else lower := pos + 115until upper < lower16return nil
Laufzeit ist , genauer im Schnitt Zugriffe.
In diesem Beispiel gehen wir davon aus, dass die Werte im Wesentlichen linear verteilt sind. Das bedeutet, dass die Differenz zwischen zwei aufeinanderfolgenden Werten immer gleich ist.
Sei beispielsweise ein Array a mit folgenden Werten geben (Auszug):
Index i | Wert |
|---|---|
i = 10 | a[i = 10] = 20.0 |
... | ... |
i = 30 | 49.5 |
... | ... |
i = 50 | 87.2 |
... | ... |
i = 70 | 151.3 |
... | ... |
i = 90 | 169.9 |
... | ... |
i = 110 | 220.0 |
... | ... |
i = 130 | 251.2 |
Wenn man jetzt exemplarisch die Paare: , und betrachtet, dann kann man zu dem Schluss kommen, dass die Funktion eine Approximation der Verteilung der Werte ist. Würde man also nach dem Wert suchen wollen, dann wäre es gut als erstes den Wert von zu überprüfen, .
In diesem Beispiel gehen wir davon aus, dass die Werte im Wesentlichen exponentiell verteilt sind. Das bedeutet, dass die Differenz zwischen zwei aufeinanderfolgenden Werten immer größer wird.
Sei beispielsweise ein Array a mit folgenden Werten geben (Auszug):
index i | a[i] |
|---|---|
0 | 0 |
... | ... |
20 | 5 |
... | ... |
50 | 25 |
... | ... |
70 | 75.7 |
... | ... |
90 | 110 |
... | ... |
110 | 380 |
... | ... |
125 | 579.5 |
... | ... |
130 | 794 |
Wenn man jetzt exemplarisch die Paare: , und betrachtet, und eine lineare Approximation durchführt, dann könnte man zu dem Schluss kommen, dass die Funktion eine gute Approximation ist.
Würde man eine quadratische Approximation mit Hilfe von Lagrange durchführen, zum Beispiel mit den Werten , , und . Dann wäre der Fehler zwischen der realen Verteilung und der angenommen deutlich geringer, da die quadratische Funktion die Werte besser approximiert.
In diesem Fall wäre die Funktion: . In diesem Fall können wir die Position des Wertes 650 im Array besser abschätzen (durch die Aufstellung der Umkehrfunktion und dann einsetzen von 650): .
Speichert unser Array kardinal skalierte Daten, so können diese modelliert werden. Das einfachste Prinzip ist die Polynominterpolation mittels Lagrange-Polynomen.
Das Ziel ist es, ein Polynom zu finden, das eine Funktion an einer gegebenen Menge von Punkten exakt interpoliert. Das heißt:
Sind Tupel reeller Zahlen gegeben mit für .
Das Lagrange-Interpolationspolynom hat dann höchstens den Grad und es gilt für alle .
Wenn zwei Punkte gegeben sind, ist das Lagrange Polynom somit:
Bei drei Punkten ist das Lagrange Polynom somit:
Der Grad unseres Lagrange-Polynoms ist immer um 1 kleiner als die Anzahl der gegebenen Punkte (die Terme des Basispolynom sind nur für definiert). Das bedeutet, dass wir für zwei Punkte ein lineares Polynom erhalten, für drei Punkte ein quadratisches Polynom, für vier Punkte ein kubisches Polynom, und so weiter. Weiterhin stellt die Konstruktion sicher, dass wir durch alle gegebenen Punkte gehen.
Bestimme p(2)
Bestimmen Sie direkt für das quadratische Polynom mit den Eigenschaften:
Bestimme p(-1)
Für die gegebenen Punkte, bestimmen Sie erst das Lagrange Polynom im Allgemeinen und rechnen Sie dann den Wert für aus.
Eine binäre Suche würde in diesem Fall mit der Position beginnen.
Hinweis
Das Lagrangepolynom kann per Konstruktion die Position der Werte und perfekt bestimmen:
Beispiel
Vom Array a sei bekannt: a[1] = 0, a[20] = 30 und a[40] = 120.
Ist der Wert im Array enthalten?
mit , und lautet:
Für den gesuchten Wert ergibt sich als zu untersuchende Position:
Bemerkung: Vandermonde-Ansatz
Alternativ kann man auch den Ansatz über die Monombasis (auch Vandermonde-Ansatz genannt) wählen.
Gegeben seien die Stützpunkte: , , , gesucht mit .
Gleichungssystem (Wert einsetzen, Index als rechte Seite):
eliminieren:
eliminieren:
Rückwärts einsetzen:
Also
Probe: ✓
Achtung!
Wenn in der Klausur explizit LaGrange erwähnt wird, dann wird eine Lösung mittels des Vandermonde Ansatzes nicht akzeptiert. Sollte die Klausur nur von quadratischer Interpolation sprechen, dann sind Sie frei in der Wahl des Vorgehens.
Zusammenfassung
Auf gleichverteilten Daten hat die lineare Interpolationssuche O(log log n).
Auf anderen Verteilungen ist lineare Interpolation oft schlechter als binäre Suche.
Quadratische Interpolation hat ein erweitertes Modell und schlägt binäre Suche häufig.
1// A durchsuchtes, 1-indiziertes, aufsteigend sortiertes Array2// needle der Wert, der gesucht wird3function linearInterpolatingSearch(A,needle)4lower := 1 // index auf das kleinste Element5upper := length(A) // index auf das größte Element6vL := A[lower]7if vL == needle then return lower8vU := A[upper]9if vU == needle then return upper10while upper > lower do11pos := round(lower·(needle−vU)/(vL−vU) +12upper·(needle−vL)/(vU−vL))13pos := max(lower + 1, min(upper - 1, pos))14value := A[pos]15if value == needle then return pos16else if value < needle then17lower := max(pos, lower+1), vL := A[lower]18else upper := min(pos, upper-1), vU := A[upper]19return nil
Bemerkung
Die Korrektur von pos in Zeile 11 (pos := max(lower + 1, min(upper - 1, pos))) stellt sicher, dass pos immer zwischen lower und upper liegt. Dies ist insbesondere deswegen notwendig, weil die Interpolation nicht immer exakt ist. Stellen Sie sich zum Beispiel vor, dass die Daten polynomiell skaliert sind und sie (in Unkenntnis der echten Verteilung) die lineare Interpolationssuche verwenden. In diesem Fall kann es zu folgender Situation kommen:
Die Werte im Array seien: [0, 4, 16, 36, 64, 100, 144, 196] (zu Grunde liegt die Funktion ) und Sie suchen nach dem Wert 194.
Im ersten Schritt würde die lineare Interpolationssuche den Wert 194 auf Position 7 schätzen, was nutzlos wäre, aber erst einmal kein Problem verursachen würde. Da der Wert 194 aber nicht im Array enthalten ist, würde die Suche den Wert für die obere Grenze um eins korrigieren. Jetzt würde die lineare Interpolation aber mit den Werten des Arrays an Stelle 0 und 6 erfolgen (A[0] = 0 und A[6] = 144). Das Ergebnis wäre die 2. Funktion (blau) und der Wert 194 würde auf Position 8 geschätzt, was außerhalb des Arrays liegt.
Folgen die Werte im Array einer logarithmisch Verteilung, dann würde die umgekehrte Situation eintreten, d. h. es könnte am unteren Ende des Arrays zu einem ähnlichen Problem kommen, da dann die Werte oberhalb der geraden liegen würden.
Wenn der berechnete Index außerhalb des Bereichs ist, dann kann der Algorithmus auch einfach nil zurückgeben, da der Wert dann nicht im Array enthalten ist.
1// A zu durchsuchendes, 1-indiziertes, aufsteigend sortiertes Array2// needle der Wert, der gesucht wird3function ExponentialSearch(A,needle)4i := 15while i <= length(A) and A[i] < needle do6i := i * 27return BinarySearch(A, floor(i/2) + 1, min(i, length(A)), needle)
Die Idee ist erst mit einer exponentiellen Schrittweite zu springen, um dann mit einer binären Suche den Wert zu finden. Die Laufzeit ist wobei die Position des gesuchten Wertes ist. Die Laufzeit ist also .
Wer sucht, der findet 5?
Folgende Werte sind vom Array A bekannt:
Gesucht wird der potentielle Index des Wertes . Welcher Index sollte als nächstes untersucht werden bei binärer, linearer oder quadratisch interpolierender Suche?
Wer sucht, der findet -1?
Folgende Werte sind vom Array A bekannt:
Gesucht wird der potentielle Index des Wertes . Welcher Index sollte als nächstes untersucht werden bei binärer, linearer oder quadratisch interpolierender Suche?
Lineare Interpolierende Suche
Setzen Sie den Algorithmus für die lineare interpolierende Suche in einer Programmiersprache Ihrer Wahl um.
Testen Sie den Algorithmus mit folgenden Arrays:
A = [1, 3, 5, 7, 9, 11, 13, 15] # linear verteilt (2x-1)
B = [0, 7, 13, 22, 27, 32, 44, 49] # approx. 7x linear verteilt
C = [0, 2, 16, 54, 128, 250, 432, 686] # quadratisch verteilt (4x^2)Wie viele Schritte (im Sinne von Schleifendurchläufen) sind maximal notwendig, um festzustellen ob ein Wert im Array enthalten ist oder nicht?
Exponentiell Interpolierende Suche
Implementieren Sie den Algorithmus für die exponentiell interpolierende Suche in einer Programmiersprache Ihrer Wahl. (Ggf. müssen Sie noch die passende binäre Suche implementieren). Implementieren Sie die Suche basierend auf einer Funktion und nicht über einem Array. Die Funktion kann zum Beispiel eine mathematische Funktion sein, oder eine einfache Funktion die auf einem Array operiert.
Gegeben sei die folgende Funktion, die als Generator fungiert. ( sei eine natürliche Zahl).
Testen Sie ob ein Wert der Funktion ist und geben Sie den Index () zurück.
Wann macht es Sinn die exponentiell interpolierende Suche zu verwenden?
Hinweise zur Implementierung
In Java kann die zu übergebene Funktion den Typ java.util.function.DoubleUnaryOperator haben. Beim Aufruf kann man dann zum Beispiel eine entsprechende Lambda-Funktion angeben werden, die für einen double Wert einen anderen double Wert zurückgibt.
Es kann hilfreich sein alle statischen Methoden und Konstanten der Math-Klasse über einen static import zu verwenden.
Die exemplarische Verwendung ist wie folgt:
1void main() {2try {3IO.println(4"Wert 64 hat Index: " + binarySearch((double x) -> 4 * x + 3, 0, 100, 64)+ "."5);6} catch (NoSuchElementException e) {7IO.println("Wert 64 nicht gefunden.");8}9IO.println(binarySearch((double x) -> (4 * x + 3), 0, 100, 43));1011try {12IO.println(13"Wert 99999996 hat Index: " +14exponentialSearch((double x) -> TODO, 99999996 )15);16} catch (NoSuchElementException e) {17IO.println("Wert 99999996 nicht gefunden.");18}19}
Sind die Daten nominal skaliert, oder sagt die Ordnung der Werte im Array nichts über die Zugriffshäufigkeit aus, so können Arrays auf Basis der Zugriffe sortiert werden.
Erfordert prinzipiell eine lineare Suche, die es gilt soweit möglich zu beschleunigen.
Anwendung(-sgebiete):
Cache-Zugriffe, Verwaltung von virtuellem Speicher
Wenn Werte häufiger verlangt werden als andere, so besitzen die Anfragen eine Wahrscheinlichkeitsverteilung.
Die Verteilung wird durch Abzählen angenähert, da sie nicht bekannt ist. Darauf basierend werden die Werte entsprechend sortiert.
Definition: FC-Regel
Ein Array A ist gemäß frequency count (FC-Regel) sortiert, wenn für alle Werte gilt, dass wenn und die realisierte Häufigkeit des Wertes darstellt.
Hinweis
Es wird typischerweise lokal getauscht, um die Ordnung herzustellen.
Definition: MF-Regel
Ein Array A ist gemäß move to front (MF-Regel) sortiert, wenn bei Auftritt eines Wertes in der Folge mit der ersten Position oder vertauscht wird, sollte der Wert noch nicht an der ersten Stelle stehen.
Definition: T-Regel
Ein Array A ist gemäß transpose (T-Regel) sortiert, wenn bei Auftritt eines Wertes in der Folge mit der Position davor vertauscht wird, sollte der Wert noch nicht an der ersten Stelle stehen.
Die FC-Regel erfordert das Mitführen der Häufigkeit der Werte. Die MF-Regel und die T-Regel sind einfacher zu implementieren, da sie nur die Reihenfolge der Werte im Array verändern.
Für MF-Regel und T-Regel gibt es worst-case Aufrufsequenzen, die immer zu den schlechtesten Laufzeiten führen.
Die MF-Regel nimmt eher starke Änderungen vor und reagiert schnell.
Die T-Regel nimmt eher schwache Änderungen vor und ist stabiler.
Zusammenfassung
Die Bewertung sollte an Hand der tatsächlichen Daten erfolgen:
Liegen Häufigkeitsinformationen vor, so ist die FC-Regel sinnvoll.
Die MF-Regel ist für sich ändernde Verteilungen sinnvoller, die T-Regel für stabilere Situationen.
A = [1,2,3,4,5] selbstanordnend sortieren
Das Array A = [1,2,3,4,5] soll selbstanordnend sortiert werden. Die gesuchten Werte sind: 1,2,3,2,3,2,1,5. Bestimmen Sie die Anordnung des Arrays nach jedem Zugriff für die Sortierungen nach MF-Regel, T-Regel und FC-Regel. Füllen Sie die nachfolgende Tabelle aus:
x | MF-Regel | T-Regel | FC-Regel | Häufigkeiten pro Wert |
|---|---|---|---|---|
1 | ||||
2 | ||||
3 | ||||
2 | ||||
3 | ||||
2 | ||||
1 | ||||
5 |
A = [1,2,3,4,5,6] selbstanordnend sortieren
Das Array A = [1,2,3,4,5,6] soll selbstanordnend sortiert werden. Danach werden die folgenden Werte in der angegebenen Reihenfolge gesucht: 5,1,6,2,3,6,5. Bestimmen Sie die Anordnung des Arrays nach jedem Zugriff für die Sortierungen nach MF-Regel, T-Regel und
FC-Regel. Füllen Sie die nachfolgende Tabelle aus:
x | MF-Regel | T-Regel | FC-Regel | Häufigkeiten |
|---|---|---|---|---|
5 | ||||
1 | ||||
6 | ||||
2 | ||||
3 | ||||
6 | ||||
5 |
Ist das Array sortiert, so ist die Suche nach dem n-ten Element trivial und hat eine Laufzeit von .
Ist das Array nicht sortiert, so ist die Suche nach dem n-ten Element nicht trivial.
Wir unterscheiden:
wird das Array (im Folgenden) auch noch sortiert gebraucht, so ist es am effizientesten dieses erst zu sortieren, um dann das n-te Element auszulesen. Die Laufzeit beträgt dann - mit der Wahl eines geeigneten Sortierverfahrens - .
Ist eine Sortierung nicht erforderlich/gewünscht, so können wir mit Hilfe von Teile-und-Herrsche-Verfahren das n-te Element auch effizienter bestimmen.
1// A ein 0-indiziertes Array2// k das k-größte Element (0-indiziert)3function Quickselect(A,k)4if length(A) == 1 then return A[0]5pivot := A[length(A)-1] // ein bel. Element als Pivot (hier das letzte)6lows := [] // Elemente kleiner als Pivot7highs := [] // Elemente größer als Pivot8pivotsCount := 0 // Anzahl der Pivot-Elemente9for x in A do // Partitionierung ...10if x < pivot then lows.append(x)11else if x > pivot then highs.append(x)12else pivotsCount := pivotsCount + 11314if k < length(lows) then15return Quickselect(lows, k)16else if k < length(lows) + pivotsCount then17return pivot // das k-te Element ist ein Pivot-Element18else19return Quickselect(highs, k - length(lows) - pivotsCount)
Hinweis
In einer realen Implementierung sollte das Pivot-Element zufällig gewählt werden, um - für den Fall, dass das Array sortiert ist - die Laufzeit zu verbessern.
Hinweis
Der Quickselect Algorithmus kann auch in-place implementiert werden, d. h. ohne zusätzlichen Speicherbedarf. Dies setzt voraus, das die ursprüngliche Reihenfolge der Elemente nicht erhalten bleiben muss.
1// A ein nicht sortiertes, 0-indiziertes Array2function FindMedian(A)3n := length(A)4if n % 2 == 1 then // d. h. wir haben eine ungerade Anzahl von Elementen in A5return Quickselect(A, floor(n / 2))6else // gerade Anzahl von Elementen in A7left := Quickselect(A, floor(n / 2) - 1)8right := Quickselect(A, floor(n / 2))9return (left + right) / 2.0
n-te Element bestimmen
Bestimmen Sie den Median für das Array A = [23,335,2,24,566,3,233,54,42,6,667,7,5,7,7]. Wenden Sie dazu den Algorithmus FindMedian (inkl. Quickselect-Algorithmus) an.
Geben Sie weiterhin nach jeder Partitionierung im Quickselect Algorithmus den aktuellen Zustand an (d. h. nach Zeile 11 in Quickselect).
Array A | k | Lows | Pivot | Pivots Count | Highs |
|---|---|---|---|---|---|
[...] | <K> | [...] | <P> | <#P> | [...] |
Komplexität von Quickselect
Bestimmen Sie die Komplexität des Quickselect-Algorithmus im schlechtesten Fall, im Durchschnittsfall und im besten Fall.
Komplexitätsanalyse
Zur Bestimmung der Komplexität kann man entweder das Master Theorem anwenden oder die Anzahl der Schritte für die Partitionierung bestimmen und die Summe der Schritte aufstellen.
Geometrische Reihen
Die Summenformel für eine geometrische Reihe () lautet:
Mit:
Summe der ersten Glieder der geometrischen Reihe.
Das erste Glied der Reihe.
Der Quotient (Verhältnis aufeinanderfolgender Glieder).
Die Anzahl der Glieder.
Für gegen unendlich und gilt somit: