Vorlesung Informatik 2 Algorithmen und Datenstrukturen (10 - Suchverfahren)Th. Ottmann
Vorlesung Informatik 2 Algorithmen und Datenstrukturen (10 - Suchverfahren)
Th. Ottmann
Problemstellung
Problem: Gegeben Folge F = (a1,...,an). Finde das Element mit Schlüssel k.
Rahmen:
class SearchAlgorithm { static int searchb(Orderable A[], Orderable k) { return search(A,k); } }
Einfachstes Verfahren: Sequentielle, lineare Suche
class SequentialSearch extends SearchAlgorithm { public static int search(Orderable A[],Orderable k){ /* Durchsucht A[1], .., A[n] nach Element k und liefert den Index i mit A[i] = k; -1 sonst */ A[0] = k; // Stopper int i = A.length; do i--; while (!A[i].equal(k)); if (i != 0) // A[i] ist gesuchtes Element return i; else // es gibt kein Element mit Schlüssel k return -1; } }
Analyse: - schlechtester Fall : n + 1
- im Mittel :
Binäre Suche
a1 an Gegeben: Folge a1, ..., an aufsteigend sortiert:
Binäre Suche
Klasse
class BinarySearch extends SearchAlgorithm
Hauptroutine
public static int search(Orderable A[],Orderable k){ /* Durchsucht A[1], .., A[n] nach Element k und liefert Index i >= 1 mit A[i] = k; 0 sonst */ int n = A.length - 1; return search(A, 1, n, k); }
Rekursiver Aufruf
public static int search(Orderable A[], int l, int r, Orderable k){ /* Durchsucht A[l], .., A[r] nach Element k und liefert Index l <= i <= r mit A[i] = k; l-1 sonst */ if (l > r) // Suche erfolglos return l-1;
int m = (l + r) / 2; if (k.less(A[m])) return search(A, l, m - 1, k); if (k.greater(A[m])) return search(A, m + 1, r, k); else // A[m] = k return m; }
Binäre Suche ohne Rekursion
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public static int search(Orderable A[], Orderable k){ int n = A.length-1, l = 1, r = n; while (l <= r) { int m = (l + r) / 2; if (k.less(A[m])) { r = m - 1; } else if (k.greater(A[m])) { l = m + 1; } else return m; } return l-1; }
Situation: Binärer Vergleichsoperator mit 3 Ausgängen; Berechnung der mittleren Position
Worst case (Annahme: n=2k-1): Suche benötigt k = log(n + 1) Vergleiche
Average Case (Annahme: n=2k-1):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Analyse
Auswertung:
Erwartungswert:
Fibonacci-Suche
Erinnerung:
F0 =0; F1=1; Fn=Fn-1 + Fn-2 für (n 2)
Verfahren:
Vergleiche den Schlüssel an Position i = Fn-2 mit k. - A[i].key > k : Durchsuche linke Fn-2 - 1 Elemente - A[i].key < k : Durchsuche rechte Fn-1 -1 Elemente
1 i N
Fn-2 - 1 Fn-1 - 1
Fn - 1
Analyse: Durchsuchen von Fn-1Elementen mit max. n Schlüsselvergleichen. Nun ist
Ergo: Cmax(N) = O(log1.618(N+1)) = O(log2N)
Implementation
public static int search(Orderable A[],Orderable k){ // Durchsucht A[1], .., A[n] nach Element k und liefert den Index i mit A[i] = k; -1 sonst int n = A.length-1; int fibMinus2 = 1, fibMinus1 = 1, fib = 2; while (fib - 1 < n) { fibMinus2 = fibMinus1; fibMinus1 = fib; fib = fibMinus1 + fibMinus2; } int offset = 0; while (fib > 1) { /* Durchsuche den Bereich [offset+1,offset+fib-1] nach Schluessel k (Falls fib = 2, dann besteht [offset+1,offset+fib-1] aus einem Element!) */ int i = min(offset + fibMinus2,n); if (k.less(A[i])) { // Durchsuche [offset+1,offset+fibMinus2-1] fib = fibMinus2; fibMinus1 = fibMinus1 - fibMinus2; fibMinus2 = fib - fibMinus1; } else if (k.greater(A[i])) { // Durchsuche [offset+fibMinus2+1,offset+fib-1] offset = i; fib = fibMinus1; fibMinus1 = fibMinus2; fibMinus2 = fib - fibMinus1; } else // A[i] = k return i; } return -1; } }
Exponentielle Suche
Index i von aj 1 2 4 8 i 16 Situation: n sehr groß, i mit ai = k klein
Ziel: Finde beliebigen Schlüssel mit einer Anzahl von Vergleichsoperationen, die logarithmisch in der Position i des gesuchten Schlüssels ist.
Eingabe: Sortierte Folge a1,...,an , Schlüssel k
Ausgabe: Index i mit ai = k
j = 1; while (k > a[j]) j = 2*j; return search (a,j/2,j,k);
Analyse: - - Binäre Suche
Gesamtaufwand: O(log i)
Interpolationssuche
al ar a l r Suchschlüssel k ? Idee: Suche von Namen im Telefonbuch, z.B. Bayer und Zimmermann
Erwartete Position von k (bei Gleichverteilung aller gespeicherten Schlüssel):
Analyse:
- im schlechtesten Fall: O(n) - im Mittel bei Gleichverteilung: O(log log n)
Das Auswahlproblem
Problem: Finde das i-kleinste Element in einer (unsortierten) Liste F mit n Elementen
1. Naive Lösung
j = 0 while (j < i) bestimme kleinstes Element a_{min} entferne a_{min} aus F; j = j + 1; return a_{min}
Anzahl der Schritte: O(i *n) für i = n/2 (Median): O(n²) (Sortieren ist besser)
2. Verfahren mit Heap
verwandle F in einen min-Heap j = 0; while (j < i) a_{min} = delete-min(F); j = j + 1; return a_{min}
Anzahl der Schritte: O(n+i*log n) für i = n/2 (Median): O(n log n)
Divide-and-Conquer-Lösung
p p Lin L> L< Idee: Aufteilung von F = a1,...,an in zwei Gruppen bzgl. Pivotelement p (Quicksort)
public static int selectIndex (Orderable A[],int i,int l,int r) { // Suche den Index des i-groessten Elementes // in A[l],...,A[r] if (r > l) { int p = pivotElement(A, l, r); int m = Quicksort.divide(A, l, r); if (i <= m - l) return selectIndex (A, i, l, m - 1); return selectIndex (A, i - (m - l), m, r); } else return l; }
Nur eine der zwei durch Aufteilung entstandenen Folgen wird weiter betrachtet.
divide-Methode von Quicksort
static int divide (Orderable A [], int l, int r) {
// teilt das Array zwischen l und r mit Hilfe
// des Pivot-Elements in zwei Teile auf und gibt
// die Position des Pivot-Elementes zurueck
int i = l-1; // linker Zeiger auf Array
int j = r; // rechter Zeiger auf Array
Orderable pivot = A [r]; // das Pivot-Element
while (true){ // "Endlos"-Schleife
do i++; while (i < j && A[i].less(pivot));
do j--; while (i < j && A[j].greater(pivot));
if (i >= j) {
swap (A, i, r);
return i; // Abbruch der Schleife
}
swap (A, i, j);
}
}
Wahl des Pivotelements
1. p = ar folgt T(n) T(n-1) + O(n)
Laufzeit im schlimmsten Fall: O(n²)
Beispiel: Auswahl des Minimums in aufsteigend sortierter Folge
2. Randomisiert
p = ein zufälliges Element aus a1,...,an
3. Median-of-Median
Bestimme Pivotelement als Median von Medianen von 5-er Gruppen
lineare Komplexität
Comments