cards-deck: 100-199_university::111-120_theoretic_cs::111_algorithms_datastructures

| Suchen in Mengen |

anchored to [[111.00_anchor]]

| Overview

Wir möchten im Folgenden die Suche von spezifischen, angefragten, Elementen in einer gewissen Menge betrachten.

| Suchen in geordneter Menge

Als einfachste Suche können wir zuerst die Suche eines Wertes x in einer Menge $M$ betrachten, wobei hier $M$ eine geordnete Menge ist . Dabei ist die Ordnung domain-spezifisch, also abhängig von dem Kriterium, nach welchem wir Sortieren wollen ( etwa größe einer Zahl, Alphabetisch etc).

[!Important] Grunddefinitionen zur Suche in geordneten Menge: Also Grundlage für die weiteren Betrachtungen der Suche definieren wir folgend:

• ein Universum $U$, welches eine lineare Ordnung aufweist. –> deckt dabei alle möglichen Einträge ab, die auftreten könnten
• eine Teilmenge $S\subset U$, welche wir als Schlüsselmenge definieren wollen
• ein beliebiges zu suchendes Element $a\in U$ ( also ein im Universum enthaltenes ELement)

Zur Suche und Arbeit in geordneten Mengen möchten wir jetzt ferner noch bestimmte Operationen definieren:

[!Definition] Grundlegende Operationen welche Operationen brauch es für eine Menge, die geordnet sein sollte? #card Wir definieren folgende Operationen in Abhängigkeit zu unserem Kontext:

Suche: $Suche(a,S)$ -> schaut nach, ob sich Element $a$ in unsere Schlüsselmenge $S$ befindet ( könnte Bool zurückgeben )

Einfügen/Insert: $insert(a,S)$ -> fügt Eintrag in die Menge ein ( dabei muss die Sortierung beibehalten werden!) Streiche/remove: $remove(a,S)$ -> entfernt Eintrag aus Menge

$ord(k,S)$ -> findet das $k-t$ größte Element in der gegebenen Menge $S$

Sortieren: $sort(S)$ -> sortiert die Menge gemäß der linearen Ordnung, die vom Universum vorgegeben ist! ^1704708938339

Es lassen sich jetzt bestimmte Grundprinzipien zur Suche von Elementen in einer geordneten Menge betrachten.

| lineare Suche

Die lineare Suche ist relativ simpel und straight forward in ihrer Implementation und Umsetzung

[!Definition] Definition Lineare Suche für eine Menge $S$, die geordnet ist, wie können wir einen Eintrag finden? #card Wir nehmen folgend ein geordnetes Array $S=\{0,\dots ,n-1\}$ an, welches wir jetzt auf bestimmte Inhalte durchsuchen möchten.

Sei hierbei jetzt $next$ der Suchindex, welcher immer bei 0 beginnt

Wir wollen jetzt die lineare Suche nach einem Inhalt $a$ einfach als PseudoCode darstellen:

while (a < S[next]){ 
  next += 1
} # inkrementiere also den Index so lange, bis wir am Index von unserem gesuchten Element angekommen sind.
if (a = S[next]) # Wert gefunden!
  return next --> also Index, den wir gefunden haben 
else 
  return null --> Eintrag nicht gefunden

Intuition wir traversieren also einfach vom anfang bis zum Ende, und wenn wir auf dem Weg auf unser Element $a$ stoßen, dann geben wir den entsprechenden Index zurück ^1704708938350

[!Important] Laufzeit der linearen Suche wie äußert sich jetzt die Laufzeit der linearen Suche? #card Wir können hier einfach die Best und Worst-Case Szenarien betrachten / vorstellen: –> Best-Case: gesuchtes Item ist an 0-ter Stelle -> $\mathcal{O}(1)$

–> Worst-Case: gesuchtes Item nicht vorhanden oder am Ende der Menge -> $\mathcal{O}(n)$

Es gibt ein ungefähres Mittel, welches suggeriert, dass: Bei $\frac{n}{2}$ Iterationen eine Laufzeit von $\mathcal{O}(n)$ hat

^1704708938358

| Binäre Suche |

Bei der linearen Suche nutzen wir nicht die Sortierung der Menge, die wir durchsuchen, aus und sind somit quasi genauso schnell, wie wenn wir in einer unsortierten Menge suchen würden.

Die Binäre Suche versucht das zu verbessern:

[!Definition] Vorgehen und Idee binärer Suche wie gehen wir bei binärer Suche vor? #card auch hier haben wir eine geordnete Menge ( als Array) vorliegen: $S=\{0,\dots ,n-1\}$. Weiterhin suchen wir wieder nach Eintrag $a$ in der Menge. Wir möchten jetzt neben der $next$ Variable -> die den aktuellen Zeiger in der Menge angibt, noch $oben$ und $unten$ definieren, welche als Abgrenzung des Suchbereiches dienen. -> Sie geben also an, wie groß der Raum unserer Menge ist, die wir betrachten und nach einem Eintrag durchsuchen möchten Wir definieren sie dabei folgend: $oben=n-1,unten=0$ Beschrieben als PseudoCode jetzt:

binary_search(A,n,T): # A is the set we look at, n the length of this set, T the queried item
left = 0 
right = n-1
while left <= right:
  m = floor(  ( L + R ) / 2 ) # position of middle elemnent, the one we are going to observe!
  if A[m] < T # so our element is larger --> to the right of it 
  	left =  m+1 ( we can discard the left side )
  else if A[m] > T # our element is smaller than the observed one 
  	right= m-1 ( we can discard the right side) 
  else:
  	return m # we found the correct item! 
#left without solution 
return failure

Intuition: Wir wollen prinzipiell in einer gewählten Menge die Mitte als Element betrachten und anschließend schauen, ob wir das richtige Element getroffen haben oder nicht. Wenn nicht, dann verkleinern wir den Bereich, in dem wir suchen ( dabei gehen wir entweder nach rechts ( gesuchtes Item ist größer als derzeitiges $S[next]<a$) oder links -> wir könenn so schrittweise verkleinern und uns einer Antwort annähnern ( wenn sie existiert) ^1704708938364

[!Important] Laufzeit von binärer Suche wie gestaltet sie sich, wie können wir das beweisen? #card Prinzipiell können wir die Laufzeit folgend konstruieren: $$T(n)=T\left(\frac{n}{2}\right)+c=\mathcal{O}(\log n)$$ (Unter Anwendung des Mastertheorems können wir mit der Laufzeit resultieren!)

Intuition: Wir wissen, dass wir nicht alle betrachten werden, weil wir quasi in einem Interall immer nur ein Item proben und diesen Intervall danach verkleinern und genauer schauen ^1704708938370

| Interpolationssuche |

Wir möchten noch eine Suche definieren, die ähnlich der Suche im Telefonbuch sein kann.

[!Important] Intuition Interpolationssuche was möchten wir hier tun, wie wird unser nächstes Element $next$ gewählt? #card Prinzipiell wird hier einfach die Wahl des gewählten Elementes anders berechnet, sodass wir schätzen, wo sich das gesuchte ELement relativ zu den anderen Einträgen befinden kann. Genauer möchten wir schätzen, wo sich $a$ relativ zu dem Eintrag bei $S[unten]$ und $S[oben]$ -> also den beiden Grenzbereichen, befindet. $$next=\lfloor \frac{a-S[unten]}{S[oben]-S[unten]}\cdot (oben-unten)\rfloor +unten$$ Mit dieser Approximation können wir jetzt immer abschätzen, wo sich das Element befinden könnte und wir betrachten es. Auch hier wenden wir den weiteren Verlauf der binary search an –> also reduzieren den Bereich, den wir durchsuchen nach und nach. ^1704708938377

[!Definition] Laufzeit von Interpolationssuche wie könnte jetzt die Laufzeit aussehen? #card Die Laufzeit ist

• im Mittel / Durchschnitt etwa: $\mathcal{O}(\log \log n)$
• Im Worst-Case etwa: $\mathcal{O}(n)$

Wir möchten noch die Mittel-Laufzeit aufschlüsseln / betrachten: $$T(n)=T(\sqrt{n})+1=T(n^{\frac{1}{2}})+1=T(n^{1{\frac{}{2}}^i)+}i=\mathcal{O}(\log \log n)$$ ^1704708938385

| Verbesserung Interpolationssuche:

Wir haben hier den Worst-Case von $\mathcal{O}(n)$, weil wir da wieder alle Elemente betrachten würden, um einen Eintrag zu finden.

Idee: Wir können jetzt den Suchbereich mit jedem Schritt verkleinern, sodas wir der Lösung immer näher kommen und weiterhin bereits durchsuchte Bereiche nicht nochmal anschauen müssen.

Wir möchten dafür den Algorithmus etwas anpassen:

[!Definition] Algorithmus was wollen wir jetzt einführen, sodass unser Algorithmus schneller wird und seinen Suchbereich weiter verkleinert? #card wir möchten zwei neue Elemente in unserer Menge aufnehmen $S[-1],S[n]$. Nach dem Prinzip möchten wir jetzt immer: iterieren, bis $a\in S$ gefunden wurde oder wir unseren Suchbereich auf 0 reduziert.

Wir definieren die Bestimmung des nächsten Eintages nun etwas anders: $$next=\lfloor \frac{a-S[unten-1]}{S[oben+1]-S[unten-1]}\cdot (oben-unten+1)\rfloor +(unten-1)$$ und weiterhin dann $n=oben-unten+1$ Wir nehmen folgende Bedinungen auf, die prüfen, ob unser Item links oder rechts vom derzeitigen Bereich ist:

if a == S[next]
  fertig, found 
if ( a > S[next]) vergleiche jetzt S[next + sqrt(n)], S[next + 2* sqrt(n)] ... --> also immer weiter suchen 
vergleiche bis: a < S [ next + ( i -1) sqrt(n)]

^1704708938393

[!Definition] Laufzeit Berechnen: unter Anwendung der besseren Vergleichsoperation, wie könenn wir diese Laufzeit jetzt neu berechnen? #card Wir wenden jetzt also $i$ Schritte an, um das Ergebnis schneller finden zu können und weniger Bereiche zu betrachten ( wir überspringen ja viele Elemente). Es erfolgt damit eine Reduktion von $n$ auf $\sqrt{n}$ Schritten.

Betrachten wir noch $C$, die die mittlere Anzahl von Vergleichen in einer Iteration angibt.

Wir behaupten jetzt, dass $C\le 2,4$ und erhalten daraus dann: $T(2)=2⟹T(n)=2+C\log \log n$ und weiter dann: $T(n)=T(\sqrt{n})+C$

Also braucht die Interpolationssuche $\le 2+2,4\log \log n$ Vergleiche im Average ^1704708938401

Dadurch ergibt sich ein neuer Worst-Case!

[!Important] Interpolationssuche Laufzeit ( und Probleme / Lösungen) wie könnte man die resultierende Laufzeit noch verbessern? #card Der Worst-Case ist jetzt mit $\sqrt{n}+\sqrt{\sqrt{n}}\cdots =\mathcal{O}((\sqrt{n}))$ beschrieben.

Man könnte das ganze noch verbessern: binäre Suche und Interpolationssuche läuft parallel durch! dann würde man eine worst-case Laufzeit von $\mathcal{O}(\log n)$ erhalten

Wichtig: die Gleichverteilungsannahme ist dann bei der Analyse wichtig, weil damit die Menge von avg-Schritten anders sein kann ^1704708938409

| Mediansuche |

Betrachten wir jetzt noch ein Prinzip der Suche, was sich etwas an dem Prinzip von [[111.33_quick_sort]] orientiert.

Wir betrachten hierbei eine Menge $S=\{1,2,\dots ,n\}$ und eine spezielle Zahl $i\le i\le n$

Wir suchen jetzt: $x\in S$ wobei dann: $\mid \{y\mid y>x\}\mid =i-1$ -> Also wir suchen ein Element, was so viele kleinere Zahlen $y$ hat, wie unser betrachtetes $i-1$

[!Definition] Umsetzung von Mediansuche Wir gehen jetzt folgend vor, um diese Suche durchzuführen:

1. Wir sortieren S und jetzt wählen wir das $i$-te Element $\mathcal{O}(1)$
2. Dieser Aufruf ist folgend: $\mathcal{O}(n\log n)$
3. Wir werden jetzt analog zu QuickSort dann diese Menge aufteilen –> wir teilen nach dem pivot-element $q$ in zwei Mengen auf:
4. Wir werden aber nur einen Teil der Menge weiter aufteilen! (verfeinert durchsuchen!)
5. Das heißt wir entscheiden uns anfangs für eine der beiden groß aufgestellten Mengen und danach werden wir nur noch in eine Richtung suchen und nach und nach verkleinern!
6. Wir haben jetzt die Mengen: $A[p,q-1],A[q+1,r]$
7. Wir wiederholen den Vorgang und suchen weiter in der neuen Partition

[!Important] PseudoCode für Random-Partition$(A,p,r)$ Wir betrachten jetzt noch den Code, der entsprechend eine Partition unserer Menge aufbaut:

Random-Select(A,p,ri)
  q = Random-Partition(A,p,r) // erstellen also eine random partitionierung der Menge und setzen diese _random-Partition_ gleich q!
  k = q - p+1
  if (i = k) then // found the correct partition of our structure !
  	return A[q]
  else if (i < k) then 
  	return Random-Select(A,p,q-1,i) //recursively calling to decrease the set to look at!
  else // 
  	return Random-Select(A,q+1,r,i-k)

| Laufzeit - Betrachtung |

Wir möchten jetzt die Laufzeit dieses Suchverfahrens betrachten.

Worst-Case: Im worst-case spalten wir unsere Partition so auf, dass wir sie mit jedem Schritt von n auf n-1 $n+(n-1)+\cdots +2+1=\mathcal{O}(n^2)$ verringern –> wir werden also mit jedem Schritt die betrachtete Partition nur um ein einziges Element verringern!

Best-Case: Im Best case werden wir mit jeder Partitionierung immer genau die Hälfte der Menge betrachten und die andere Hälfte loswerden. Es folgt hierbei dann: $$n+\frac{n}{2}+\frac{m}{4}+\cdots +2+1\le 2n$$

Average Case: Ähnlich, wie es bei Quicksort notwendig war den avg-case durch die Betrachtung der Normalverteilung der Elemente in einer Menge zu bestimmen, müssen wir auch hier so vorgehen, um eine Aussage treffen zu können:

Sei hierbei jetzt $T(n)$ eine Zufallsvariable für die Laufzeit des Algorithmus. Die Funktion Random-Partition zerlegt hierbei die Menge immer mit einer Wahrscheinlichkeit von $1/n$ in neue, kleinerer Teilmengen mit der Größe $k,n-k$ ( also hier zwei Mengen!)

Für entsprechende $k=1,2,\dots ,n$ definieren wir jetzt noch eine $0/1$-Zufallsvaraible $X_k$ mit $X_k=1,\text{ wenn }|A[p,q]|=k$, also immer dann, wenn $A[p,q]$ $k$ Elemente aufweist! Es folgt aus dieser Betrachtung dann, dass: $E(X_K)=1/n$ –> weil wir das ja für $n$ solche Variablen betrachten!

[!Tip] Beobachtung zur Laufzeit: Wir sehen jetzt hier, dass $T(n)$ monoton ist! Damit ist also die Laufzeit größer, wenn $i$ in einer großen Teilmenge auftritt, weil man es dann entsprechend länger suchen muss!

[!Warning] Behauptung für die Laufzeit Unter Konstruktion einer oberen Schranke können wir jetzt noch zeigen, dass dieser Algorithmus $E(T(n))\le c\cdot n$ für ein konstante s $c$ sein wird!

Sei dafür: $$\begin{array}{rl}T(n)\le & \sum _{k=1}^n(X_K\cdot (T(\max (k-1,n-k))+\mathcal{O}(n)))\\ =& \sum _{k=1}^n(X_K\cdot T(\max (k-1,n-k))+\mathcal{O}(n))\end{array}$$ und weiterhin können wir dann einsetzen und folgend bestimmen: $$\begin{array}{rl}E(T(n))=& E\left(\sum _{k=1}^n(X_K\cdot T(\max (k-1,n-k))+\mathcal{O}(n))\right)\\ =& \sum _{k=1}^{n}E\cdot (X_K\cdot T(\max (k-1,n-k))+\mathcal{O}(n))\\ =& \sum _{k=1}^{n}E\cdot (X_K)\cdot E(T(\max (k-1,n-k)))+\mathcal{O}(n))\\ =& \sum _{k=1}^{n}1\frac{}{n\cdot E(T(\max (k-1,n-k)))}+\mathcal{O}(n)\\ =& 2/n\cdot \sum _{k=n/2}^{n-1}E(T(k))+\mathcal{O}(n)\end{array}$$

Wir möchten jetzt noch unsere Behauptung bestätigten / widerlegen. Betrachte also nochmal die Behauptung:

[!Tip] Behauptung zur Laufzeit Wir gehen davon aus, dass $E(T(n))\le c\cdot n$ whenever $c$ ist konstant

Wir können diese Umstand jetzt durch Anwendung von Induktion und dem vorherigen Einsetzen beweisen:

Beweis: Wir wissen, dass $T(n)=\mathcal{O}(1)$, wenn $n$ konstant ist. Wir wollen das jetzt zeigen: $$\begin{array}{rlr}E(T(n))& =2/n\cdot \sum _{k=n/2}^{n-1}(E(T(k))+\mathcal{O}(n))& \\ & =2/n\cdot \sum _{k=n/2}^{n-1}c\cdot k+n& \text{fu¨r die Konstanten }c,d\\ & =2\cdot c/n\left(\sum _{k=1}^{n-1}k-\sum _{k=1}^{\frac{n}{2-1}k}\right)+d\cdot n& \text{ weiterhin sind sie Konstanten!}\\ & \le 2c/n\cdot \left(n^2\frac{1}{2}-{\left(\frac{n}{2}\right)}^2\frac{1}{2}\right)+d\cdot n& \\ & =\frac{2c}{n}\cdot \left(\frac{3}{8}\cdot n^2\right)+d\cdot n& \\ & =\frac{3c}{4}\cdot +d\cdot n& \\ & \le c\cdot n& \text{falls jetzt folgend! }d\le \frac{c}{4}\end{array}$$

| Deterministische Auswahl treffen |

In der vorherigen Betrachtung haben wir nur mit einer randomisierten Suche gearbeitet, also einfach beliebig Elemente als Median genommen, um dann das entsprechende Element zu finden.

Jetzt möchten wir eine deterministische Variante betrachten: <<–Motivation–>>: Wenn wir den Median schnell finden können, dann sollte das auch für das i-te größte Element funktionieren!

[!Definition] Definition der deterministischen Auswahl | Wir adaptieren / verändern unsere Auswahl Funktion jetzt noch ein wenig und konstruieren sie mit folgenden Schritten

1. Teile Menge S in $\frac{n}{5}$ Gruppen der Größe $5$
2. In jeder dieser Gruppen bestimmen wir jetzt den Median!
3. Rekursiv bestimmen wir jetzt noch den Median x der ganzen Mediane ( die wir zuvor berechnet haben!)
4. Wir teilen die Menge $S$ ( Eingabemenge!) unter Anwendung des Gesamt-Medianes $x$ in zwei Gruppen $S_1,S_2$ und hierbei dann: $\mid S_1\mid =k-1$
5. Folgende Fallentscheidung folgt jetzt:
6. Wenn jetzt: $(i==k)$ dann geben wir x zurück!
7. Wenn stattdessen $i<k$, dann geben wir rekursiv zurück: $Auswahl(S_1,i)$ –> also eine kleinere Menge, die wir betrachten werden
8. Und wenn das auch nicht eintritt, folgt jetzt noch: $Auswwahl(S_2,i-k)$ als der neue Aufruf, um rekursiv zu partitionieren

[!Important] Motivation dieser Aufteilung in $5$ Teile: Durch dies Aufteilung können wir jetzt halt ganz einfach approximieren, wie viele Mediane - die wir in den kleineren Untergruppen entnehmen / konstruieren - dann größer sein werden als das gesuchte $x$! Also $\frac{1}{2}\cdot \frac{n}{5}$ der Mediane werden die Eigenschaft aufweisen

Diese Gruppen werden dann immer alle $\ge 3$ Elemente aufweisen, die in ihrere Struktur $>x$ sind! Daraus folgt jetzt => Es gibt $\ge \frac{3}{10}\cdot n$ größere und somit (analog auch) $\ge \frac{3}{10}\cdot n$ kleinere Mediane, als der Referenzwert $x$ Daraus folgt jetzt: $$\left(\mid S_1\mid ,\mid S_2\mid \le \frac{7}{10}\cdot n\right)⟹x\text{ ist eine gute Wahl dafu¨r! }$$ Denn folgend sehen wir: $T(n)=T\left(\frac{n}{5}\right)+T\left(\frac{7}{10n}\right)+\mathcal{O}(n)$

Wir wollen diese Folgerung ferner unter der vorherigen Betrachtung evaluieren. Schauen wir also nochmal darauf:

[!Info] Beweisen der Behauptung $T(n)\le c\cdot n$ Wir beweisen diese Behauptung jetzt durch Anwendung der vorherigen Ergebnisse: Wieder stimmt sie für ein konstantes $n$ und somit ist der IA gesetzt. Induktionsschritt: $$\begin{array}{rlr}>T(n)& \le c\cdot \frac{n}{5}+\cdot \frac{7}{10n}+d\cdot n& \\ >& =c\cdot \frac{9}{10n}+d\cdot n& \\ >& =c\cdot n& \text{ fu¨r }d=\frac{c}{10}>\end{array}$$

| Laufzeit Mediansuche |

[!Important] Folgerung / Definition Wir können in einer ungeordneten Menge der Große $n$ das **i-**tgrößte Element in einer Zeit von $\mathcal{O}(n)$ finden!