michael.eichberg@dhbw.de, Raum 149B
1.1.4
Die Folien sind teilweise inspiriert von oder basierend auf Lehrmaterial von Prof. Dr. Ritterbusch
Welche Skalierung haben gesuchte Daten sind im Array?
Nur Vergleich auf Gleichheit, keine natürliche Ordnung oder Zahlbegriff.
Es gibt Größenvergleiche und damit eine Sortierung, aber kein Zahlbegriff.
Es gibt Größenvergleiche und Zahlbegriff.
Unsortiert oder nominal führt (zunächst) zur linearen Suche.
Ordinale und kardinale Werte können sortiert werden für binäre Suche.
Kardinale Größen können modelliert werden für interpolierende Suche.
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.4
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.
1Algorithm linearSearch(A,n,needle)2for i= 1,...,n do3if A[i] == needle then4return i5return nil
Laufzeit und Elementzugriffe kann asymptotisch durch \(O(n)\) abgeschätzt werden.
Wiederholung
1Algorithm binarySearch(A,l,u,needle)2upper = u3lower = l4repeat5pos = round((upper+lower)/2)6value = A[pos]7if value == needle then8return pos9else if value > needle then10upper = pos−111else12lower = pos + 113until upper < lower14return nil
Laufzeit ist \(O(\log(n))\), genauer im Schnitt \(\log_2(n)-1\) Zugriffe.
Wiederholung
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: \((i = 10, a[i] = 20.0)\), und \((i = 110, a[i] = 220)\) betrachtet, dann kann man zu dem Schluss kommen, dass die Funktion \(f(x) = 2.0\cdot x\) eine Approximation der Verteilung der Werte ist. Würde man also nach dem Wert \(a[i] = y = 170\) suchen wollen, dann wäre es gut als erstes den Wert von a[85] zu überprüfen, \(170 = 2\cdot x \rightarrow \frac{170} {2} = 85 = i\).
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):
x |
y |
|---|---|
0 |
0 |
... |
... |
20 |
5 |
... |
... |
50 |
25 |
... |
... |
70 |
75.7 |
... |
... |
90 |
110 |
... |
... |
110 |
380 |
... |
... |
125 |
579.5 |
... |
... |
130 |
794 |
Wenn man jetzt exemplarisch die Paare: \((i = 20, a[i] = 5.0)\), und \((i = 130, a[i] = 794)\) betrachtet, und eine lineare Approximation durchführt, dann könnte man zu dem Schluss kommen, dass die Funktion \(f(x) = 6.1\cdot x\) eine gute Approximation ist.
Würde man eine quadratische Approximation mit Hilfe von Lagrange durchführen, zum Beispiel mit den Werten \((i = 20, a[i] = 5.0)\), \((i = 90, a[i] = 110)\) , und \((i = 130, a[i] = 794)\). 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 Fall wäre die Funktion: \(p(x) = \frac{39}{275}x^2 - \frac{141}{10}x + \frac{2533}{11}\) 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): \(\approx 123\).
Beispiel:
Wenn wir wissen, dass die Werte quadratisch verteilt sind (Array[10] a = { 1, 4, 9,16, ..., 100 }), und wir zum Beispiel wissen, dass der kleinste Wert im Array \(1\) und der größte Wert \(100\) (an Stelle/mit Index \(10\)) ist, den wir im Array gespeichert haben, dann macht es „keinen“ Sinn den Wert \(85\) oder \(5\) in der Mitte zu suchen! (\(85\) findet sich vermutlich an Stelle \(9 = \lfloor\sqrt{85}\rfloor\)).
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 \(p(x)\) zu finden, das eine Funktion \(f(x)\) an einer gegebenen Menge von Punkten \((x_1, y_1), \dots, (x_n, y_n)\) exakt interpoliert. Das heißt:
Sind \(n\) Tupel \((x_n ,y_n ) \in \mathbb{R}^2\) reeller Zahlen gegeben mit \(x_l \neq x_m\) für \(l \neq m\).
Das Lagrange-Interpolationspolynom hat dann höchstens den Grad \(n-1\) und es gilt \(p(x_i ) = y_i\) für alle \(i= 1,...,n\).
Beispiel
Gegeben sein die zwei Punkte: \((x_1, y_1) = (1, 2)\) und \((x_2, y_2) = (3, 4)\).
Das Lagrange-Polynom \(p(x)\) wäre dann:
Nach Ausmultiplizieren und Zusammenfassen ergibt das ein Polynom, das durch beide Punkte verläuft.
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 \(j \neq i\) 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 \(p(2)\) für das quadratische Polynom mit den Eigenschaften:
Bestimme p(-1)
Für die gegebenen Punkte, bestimmen Sie erst das Lagrange Polynom \(p(x)\) im Allgemeinen und rechnen Sie dann den Wert für \(p(-1)\) aus.
Beispiel
Vom Array a sei bekannt: a[1] = 0, a[20] = 30 und a[40] = 120.
Ist der Wert 50 im Array enthalten?
Das Lagrangepolynom \(p(x)\) mit \(p(30) = 20\) und \(p(120) = 40\) lautet:
Für den gesuchten Wert 50 ergibt sich als zu untersuchende Position:
Eine binäre Suche würde in diesem Fall mit der Position \({40+20 \over 2} = 30\) beginnen.
Beispiel
Vom Array a sei bekannt: a[1] = 0, a[20] = 30 und a[40] = 120.
Ist der Wert 50 im Array enthalten?
\(p(x)\) mit \(p(0) = 1\), \(p(30) = 20\) und \(p(120) = 40\) lautet:
Für den gesuchten Wert 50 ergibt sich als zu untersuchende Position:
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.
1Algorithm linearInterpolatingSearch(A,needle)2lower := 1 // index auf das kleinste Element3upper := length(A) // index auf das größte Element4vL := A[lower]5if vL == needle then return lower6vU := A[upper]7if vU == needle then return upper8while upper > lower do9pos := round(lower·(needle−vU)/(vL−vU) +10upper·(needle−vL)/(vU−vL))11pos := max(lower + 1, min(upper - 1, pos))12value := A[pos]13if value == needle then return pos14else if value < needle then15lower := max(pos, lower+1), vL = A[lower]16else17upper := min(pos, upper-1), vU = A[upper]18return nil
Die Korrektur von pos in Zeile 11 (pos := max(lower + 1, min(upper - 1, pos))) stellt sicher, dass pos immer strikt 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 \(4x^2\)) 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.
1Algorithm ExponentialSearch(A,needle)2i = 13while A[i] < needle do4i = i * 25return BinarySearch(A,floor(i/2) + 1,i,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 \(O(\log(i))\) wobei \(i\) die Position des gesuchten Wertes ist. Die Laufzeit ist also \(O(\log(n))\).
Wer sucht, der findet 5?
Folgende Werte sind vom Array A bekannt:
\(A[1] = -27,\; A[15] = 13,\; A[29] = 29\)
Gesucht wird der potentielle Index des Wertes 5. Welcher Index i 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:
\(A[1] = -13,\; A[7] = -4,\; A[13] = 11\)
Gesucht wird der potentielle Index des Wertes -1. Welcher Index i 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. linear verteilt (approx. 7x)
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).
Gegeben sei die folgende Funktion, die als Generator fungiert. (\(x\) sei eine natürliche Zahl).
Testen Sie ob \(99999996\) ein Wert der Funktion ist und geben Sie den Index (\(x\)) zurück.
Wann macht es Sinn die exponentiell interpolierende Suche zu verwenden?
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.
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.
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 |
Texte können als unsortierte Arrays von Zeichen verstanden werden. Eine typische Frage ist hier das Finden von Textsequenzen im Text.
1Algorithmus NaiveTextSearch(text,needle)2n = length(text)3m = length(needle)4for i = 1,...,n-m + 1 do5j = 06while text[i + j] == needle[j + 1] do7j = j + 18if j == m then9return i // Found at i10return nil
Beispiel bei einfacher Suche nach aaab in aaaaaaaab:
a a a a a a a a b
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
a a a b̶
a a a b̶
a a a b̶
a a a b̶
a a a b̶
a a a b
Sind so viele Vergleiche notwendig?
Das Verfahren von Knuth-Morris-Pratt vermeidet unnötige Vergleiche, da es zunächst die Suchwortteile auf den größten Rand, also das größte Prefix, das auch Postfix ist, untersucht.
Beispiel/Idee
Text 010110101 Gesucht/Muster 010101 Übereinstimmung ✓✓✓✓✗
Beobachtungen:
Wir haben an Stelle 5 ein Mismatch.
Wenn wir im Text das Muster um eine Stelle nach rechts verschoben suchen, so haben wir garantiert wieder ein Mismatch.
Beispiel/Idee
1. 2. Text 01101100 0102111 Gesucht/Muster 01100 010201 Übereinstimmungen ✓✓✓✓✗ ✓✓✓✓✗
Beobachtungen bzgl.:
Beim Mismatch an Stelle 5 kann das Muster „nur“ um 3 Stellen nach rechts verschoben werden.
Beim Mismatch an Stelle 5 kann das Muster um 4 Stellen nach rechts verschoben werden.
Wie weit wir das Muster verschieben können, hängt also vom Rand des Teils des Musters ab, der bereits übereinstimmt.
Beispiel
Das Wort \(aufkauf\) hat die echten Präfixe und Postfixe:
\(\{p^{(k)} : 0 \leq k <n\}=\{\varepsilon ,a,au,auf,aufk,aufka,aufkau\}\)
\(\{q^{(k)} : 0 \leq k <n\}=\{\varepsilon ,f,uf,auf,kauf,fkauf,ufkauf\}\)
und die Ränder:
\(\{r^{(k)} : 0 \leq k <n\}= \{\varepsilon ,auf\}\).
Das bedeutet, dass wenn \(aufkauf\) erkannt wurde, die letzten drei Buchstaben schon den nächsten Treffer einleiten können, wie beispielsweise in \(aufkaufkauf\).
Das KMP-Verfahren fängt nicht immer von vorne an, sondern prüft, ob ein Rand eines Präfixes \(- \varepsilon \) ausgenutzt werden kann. Dazu werden die entsprechenden größten Ränder bestimmt.
Beispiel: ananas
Präfixe \(\setminus \{\varepsilon \}\) |
Größter Rand |
Länge des Randes |
|---|---|---|
a |
ε |
0 |
an |
ε |
0 |
a̲na̅ |
a |
1 |
a̲n̲a̅n̅ |
an |
2 |
a̲n̲a̲̅n̅a̅ |
ana |
3 |
ananas |
ε |
0 |
Beispiel: axaaxax
\(Präfixe \setminus \{\varepsilon \}\) |
Größter Rand |
Länge des Randes |
|---|---|---|
a |
ε |
0 |
ax |
ε |
0 |
a̲xa̅ |
a |
1 |
a̲xaa̅ |
a |
1 |
a̲x̲aa̅x̅ |
ax |
2 |
a̲x̲a̲a̅x̅a̅ |
axa |
3 |
a̲x̲aaxa̅x̅ |
ax |
2 |
Die Idee ist also, dass wir beim Musterabgleich nach einem Mismatch, wenn der übereinstimmende Teil einen Rand hat, beim Abgleich des Musters an einer späteren Stelle - basierend auf der Größe des Randes - weitermachen können. Wir müssen also nicht immer das ganze Muster von vorne anfangen zu vergleichen.
Ränder und Randlängen bestimmen
Bestimmen Sie die Ränder und die Längen der \(Präfixe - \varepsilon \) für die Worte:
\(tultatul\)
\(eikleike\)
\(okokorok\)
\(trattrad\)
1Algorithm ComputePrefixFunction(needle)2m = length(needle)3sei B[1...m] ein Array // Array für die Längen der Ränder der Teilworte4B[1] = 05j = 0 // j ist die Länge des Randess6for i = 2,...,m do7j = j + 18while j > 0 and needle[j] ≠ needle[i] do9if j > 1 then10j = B[j-1] + 111else12j = 013B[i] = j14return B
Komplexität: \(O(m)\)
1Algorithm KMP(text,needle)2n = length(text), m = length(needle)3B = ComputePrefixFunction(needle)4q = 0 // Anzahl der übereinstimmenden Zeichen5R = [] // Ergebnisliste der Indizes der Übereinstimmungen6for i = 1,...,n do7while q > 0 and needle[q + 1] ≠ text[i] do8q = B[q] // ... die nächsten Zeichen stimmen nicht überein9if needle[q + 1] == text[i] then10q = q + 1 // Übereinstimmung11if q == m then12R append (i - m + 1)13q = B[q] // Suche nach nächster Übereinstimmung14return R
Komplexität: \(O(n+m)\)
Details ComputePrefixFunction
Die Funktion \(ComputePrefixFunction\) berechnet die größten Werte der Präfixe für das Suchwort \(needle\) der Länge \(m\) und gibt diese als Array (\(B\)) zurück. Das Array \(B\) enthält somit die größten Ränder der Präfixe \(needle[1,...,i]\). (Der Wert von \(B[1]\) ist immer 0, da es keinen Rand gibt.)
Gesucht wird ananas in saansanananas
s a a n s a n a n a n a s i ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ 1 a̶ ... 3 a n̶ ... 5 a n a̶ ... 11 a n a n a s̶ Beim Auftreten des Mismatch (Zeile 7) ist ... q = 5 und wird auf p[5] = 3 (Zeile 8) gesetzt 13 a n a n a s
Dargestellt sind die Fälle, in denen ein Mismatch auftritt. i ist der Index des aktuellen Zeichen im Text, das mit dem Muster verglichen wird.
KMP-Algorithmus
Bestimmen Sie die Randlängen der Muster und stellen Sie die Teilschritte bei der Durchführung des KMP-Algorithmus zur Suche des Wortes/Muster im Text dar.
Stellen Sie insbesondere die Fälle dar in denen ein Mismatch auftritt.
Muster |
Text |
|---|---|
aaab |
aaaaaaaab |
barbara |
abbabarabarbarbara |
Der Algorithmus vergleicht das Muster (Pattern) von rechts nach links mit dem Text.
Viele andere Algorithmen führen die Vergleiche von links nach rechts durch.
Der Boyer-Moore-Algorithmus nutzt dies aus, indem er die Verschiebung des Musters anhand des letzten Zeichens des Musters und des Textes vornimmt.
Wird beispielsweise das Wort Banane im Text Orangen,␣Ananas␣und␣Bananen gesucht, so wird zunächst die Sprungtabelle für das verwendete Alphabet in Bezug auf das Suchwort (Banane mit Länge 6) bestimmt:
Zeichen im Text |
␣ |
, |
A |
B |
O |
a |
d |
e |
g |
n |
r |
s |
u |
Sprung |
6 |
6 |
6 |
5 |
6 |
2 |
6 |
0 |
6 |
1 |
6 |
6 |
6 |
O r a n g̲ e̲ n , ␣ A n̲ a̲ n a̲ s ␣̲ u n d ␣ B̲ a̲ n̲ a̲ n̲ e̲ n̲
B a n a n̶̲ e̶̲
B a n a n e̶̲
B a n a n e̶̲
B a n a n e̶̲
B a n a n e̶̲
B a n a n e̶̲
B a n a n e̶̲
B̲ a̲ n̲ a̲ n̲ e̲
B a n a n e̶̲
Unterschrichen sind die durchgeführten Vergleiche. Die Verschiebung des Musters erfolgt anhand des letzten Zeichens des Musters und des Textes, dass nicht übereinstimmt. Dabei ist die Verschiebung durch das Zeichen des Textes gegeben, das nicht mit dem Muster übereinstimmt.
Komplexität
Im guten und häufigen Fall erreicht das Verfahren \(O(\frac{n}{m})\), aber in speziellen Fällen ist auch \(O(n·m)\) möglich.
Bei der Sprungtabelle handelt es sich um eine Tabelle, die für jedes Zeichen des Alphabets des Textes die Verschiebung des Musters angibt, wenn das Zeichen im Text mit dem Muster nicht übereinstimmt. Die Zeichen A, O, d, g, r, s, u, , und das Leerzeichen haben die größte Verschiebung, da sie nicht im Muster vorkommen. Das Zeichen e hat die kleinste Verschiebung, da es das letzte Zeichen des Musters ist. Das Zeichen n hat eine Verschiebung von 1, da es im Muster als vorletztes Zeichen vorkommt, das Zeichen a hat eine Verschiebung von 2, da das späteste Vorkommen an drittletzer Stelle ist, und das Zeichen B hat eine Verschiebung von 5, da es nur einmal vorkommt und das erste Zeichen des Musters ist.
„belli“
Suchen Sie das Wort
belli
im Text
It is a dark time for the Rebellion.
"barbara"
Suchen Sie das Wort
barbara
im Text
abbabarabarbarbara
Ist das Array sortiert, so ist die Suche nach dem n-ten Element trivial und hat eine Laufzeit von \(O(1)\).
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 - \(O(n \log n)\).
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.
1Algorithm Quickselect(A,k) // gesucht ist das k größte Element2if length(A) == 1 then return A[0]3pivot := A[length(A)-1] // ein bel. Element als Pivot (hier das letzte)4lows := [] // Elemente kleiner als Pivot5highs := [] // Elemente größer als Pivot6pivotsCount := 0 // Anzahl der Pivot-Elemente7for x in A do // Partitionierung ...8if x < pivot then lows.append(x)9else if x > pivot then highs.append(x)10else pivotsCount := pivotsCount + 11112if k < length(lows) then13return Quickselect(lows, k)14else if k < length(lows) + pivotsCount then15return pivot // das k-te Element ist ein Pivot-Element16else17return Quickselect(highs, k - len(lows) - pivotsCount)
1Algorithm FindMedian(A) // A ist _nicht sortiert_2n = length(A)3if n % 2 == 1 then // d. h. wir haben eine ungerade Anzahl von Elementen in A4return Quickselect(A, floor(n / 2))5else // gerade Anzahl von Elementen in A6left = Quickselect(A, floor(n / 2) - 1)7right = Quickselect(A, floor(n / 2))8return (left + right) / 2
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 (\(S_n = a + ar + ar^2 + \dots + ar^{n-1}\)) lautet:
Mit:
- \(S_n\):
Summe der ersten \(n\) Glieder der geometrischen Reihe.
- \(a\):
Das erste Glied der Reihe.
- \(r\):
Der Quotient (Verhältnis aufeinanderfolgender Glieder).
- \(n\):
Die Anzahl der Glieder.
Für \(n\) gegen unendlich und \(|r| < 1\) gilt somit: