Kurs:Algorithmen und Datenstrukturen/Vorlesung/Fibonacci Suche

From Wikiversity
Jump to navigation Jump to search



Fibonacci Suche[edit]

Dieses Kapitel behandelt die Fibonacci Suche. Die im vorherigen Kapitel behandelte binäre Suche hat Nachteile. Die binäre Suche ist der am häufigsten verwendete Algorithmus zur Suche in sortierten Arrays. Die Sprünge zu verschiedenen Testpositionen sind allerdings immer recht groß. Dies kann nachteilig sein, wenn das Array nicht vollständig im Speicher vorliegt (oder bei Datenträgertypen wie Kassetten). Außerdem werden neue Positionen durch Division berechnet und je nach Prozessor ist dies eine aufwändigere Operation als Addition und Subtraktion. Daher nehmen wir die Fibonacci Suche als eine weitere Alternative.

Fibonacci Zahlen[edit]

Zur Erinnerung, die Folge der Fibonacci Zahlen für ist definiert durch




 für 
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

Anstatt wie bei der binären Suche das Array in gleich große Teile zu teilen, wird das Array in Teilen entsprechend der Fibonacci-Zahlen geteilt Es wird zunächst das Element an Indexposition m betrachtet, wobei m die kleinste Fibonaccizahl ist, die größer als die Arraylänge ist. Nun fährt man rekursiv mit dem entsprechenden Teilarray fort.

Rekursive Fibonacci Suche[edit]

public int fibonacciSearch(int[] arr, int elem) {
	return fibonacciSearchRec(arr,elem,0,arr.length-1);
}

public int fibonacciSearchRec(int[] arr, int elem, int u, int o) {
	int k = 0;
	while (fib(k) < o-u) k++;
	if (elem == arr[u+fib(--k)])
		return u+fib(k);
	if (u == o)
		return -1;
	if (elem < arr[u+fib(k)])
		return fibonacciSearchRec(arr, elem, u, u+fib(k)-1);
	return fibonacciSearchRec(arr ,elem, u+fib(k)+1, o);
}

Beispiel[edit]

9 19 21 34 87 102 158 159 199 205

Wo befindet sich die 133?

  1. fibonacciSearchRec(arr,133,0,9)
    1. fib(6)=8 < 9-0 (und maximal)
    2. arr[fib(6)+0] = arr[8] = 199 > 133
  2. fibonacciSearchRec(arr,133,0,7)
    1. fib(5)=5 < 7-0 (und maximal)
    2. arr[fib(5)+0] = arr[5] = 102 < 133
  3. fibonacciSearchRec(arr,133,6,7)
    1. fib(0)=0 < 7-6 (und maximal)
    2. arr[fib(0)+6] = arr[6] = 158 > 133
  4. fibonacciSearchRec(arr,133,6,6)
    1. Suche erfolglos

Wo befindet sich die 87?

  1. fibonacciSearchRec(arr,87,0,9)
    1. fib(6)=8 < 9-0 (und maximal)
    2. arr[fib(6)+0] = arr[8] = 199 > 87
  2. fibonacciSearchRec(arr,87,0,7)
    1. fib(5)=5 < 7-0 (und maximal)
    2. arr[fib(5)+0] = arr[5] = 102 > 87
  3. fibonacciSearchRec(arr,87,0,4)
    1. fib(4)=3 < 4-0 (und maximal)
    2. arr[fib(4)+0] = arr[3] = 34 < 87
  4. fibonacciSearchRec(arr,87,4,4)
    1. Suche erfolgreich

Aufwands Analyse[edit]

Die Fibonacci Suche hat dieselbe Komplexität wie die binäre Suche. Die Anzahl der Vergleiche im besten Fall ist 1 und die Anzahl der Vergleiche im Durchschnitt (erfolgreich/erfolglos) und im schlechtesten Fall ist . Die nötigen Fibonaccizahlen können vorab berechnet und in einem (statischen) Array gespeichert werden. Für Arrays mit weniger als 100.000.000 Elementen werden “nur” die ersten 50 Fibonaccizahlen benötigt. Als Operationen können nur Subtraktion und Addition genutzt werden und die “Sprünge” zwischen Arrayposition ist im Durchschnitt geringer als bei binärer Suche.


Vorheriges Thema.jpg Discussion Nächstes Kapitel .jpg