Fibonacci-Suche

1. Fibonacci-Suchalgorithmus
2. Beispiel für die Fibonacci-Suche
3. Implementierung des Fibonacci-Suchalgorithmus
4. Komplexität des Fibonacci-Suchalgorithmus

Die Fibonacci-Suche ist ein effizienter Intervall-Suchalgorithmus. Er ähnelt der Binären Suche in dem Sinne, dass er ebenfalls auf der Divide-and-Conquer-Strategie basiert und das Array ebenfalls sortiert werden muss. Außerdem ist die Zeitkomplexität für beide Algorithmen logarithmisch. Es wird Fibonacci-Suche genannt, weil es die Fibonacci-Reihe nutzt (Die aktuelle Zahl ist die Summe zweier Vorgänger F[i] = F[i-1] + F[i-2], F[0]=0 &F[1]=1 sind die ersten beiden Zahlen in der Reihe.) und das Array in zwei Teile mit der durch die Fibonacci-Zahlen gegebenen Größe unterteilt. Es ist eine rechenfreundliche Methode, die nur Additions- und Subtraktionsoperationen verwendet, im Vergleich zu Division, Multiplikation und Bit-Verschiebungen, die bei der binären Suche erforderlich sind.

Fibonacci-Suchalgorithmus

Nehmen wir an, wir haben ein unsortiertes Array A[], das n Elemente enthält, und wir wollen ein Element finden - X.

Beispiel für die Fibonacci-Suche

Angenommen, wir haben das Array: (1, 2, 3, 4, 5, 6, 7). Wir müssen nach dem Element X = 6 suchen.

Das Array hat 7 Elemente. Also ist n = 7. Die kleinste Fibonacci-Zahl, die größer als n ist, ist 8.

Implementierung des Fibonacci-Suchalgorithmus

#include <bits/stdc++.h>
using namespace std;

int fibonacciSearch(int A[], int x, int n) {
  int fbM2 = 0;
  int fbM1 = 1;
  int fbM = fbM2 + fbM1;
  int offset = -1;
  while (fbM < n) {
    fbM2 = fbM1;
    fbM1 = fbM;
    fbM = fbM2 + fbM1;
  }
  while (fbM > 1) {
    int i = min(offset + fbM2, n - 1);
    if (A[i] < x) {
      fbM = fbM1;
      fbM1 = fbM2;
      fbM2 = fbM - fbM1;
      offset = i;
    } else if (A[i] > x) {
      fbM = fbM2;
      fbM1 = fbM1 - fbM2;
      fbM2 = fbM - fbM1;
    } else
      return i;
  }
  if (fbM1 && A[offset + 1] == x) return offset + 1;

  return -1;
}

int main() {
  int n = 9;
  int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  int x = 8;
  int result = fibonacciSearch(arr, x, n);
  if (result == -1) {
    cout << "Element not found !!";
  } else
    cout << "Element found at index " << result;
  return 0;
}

Komplexität des Fibonacci-Suchalgorithmus

Zeitkomplexität

• Durchschnittlicher Fall

Wir reduzieren den Suchraum in jeder Iteration um ein Drittel / zwei Drittel, daher hat der Algorithmus eine logarithmische Komplexität. Die Zeitkomplexität des Fibonacci-Suchalgorithmus ist O(logn).

• Bester Fall

Die Zeitkomplexität im besten Fall ist O(1). Sie tritt auf, wenn das zu suchende Element das erste Element ist, das wir vergleichen.

• Schlechtester Fall

Der ungünstigste Fall tritt ein, wenn das Zielelement X immer in dem größeren Subarray vorhanden ist. Die Zeitkomplexität im schlimmsten Fall ist O(logn). Sie ist identisch mit der Zeitkomplexität im mittleren Fall.

Raumkomplexität

Die Platzkomplexität dieses Algorithmus ist O(1), da außer temporären Variablen kein weiterer Platz benötigt wird.