Springen Suche

1. Sprung-Such-Algorithmus
2. Beispiel für Sprungsuche
3. Implementierung des Sprungsuchalgorithmus
4. Komplexität des Sprungsuchalgorithmus

Die Sprungsuche ist ein Intervall-Suchalgorithmus. Es ist ein relativ neuer Algorithmus, der nur auf sortierten Arrays funktioniert. Er versucht, die Anzahl der erforderlichen Vergleiche gegenüber der linearen Suche zu reduzieren, indem er nicht wie die lineare Suche jedes einzelne Element durchsucht. Bei der Sprungsuche wird das Array in m Blöcke unterteilt. Es wird das Element in einem Block gesucht und, wenn das Element nicht vorhanden ist, wird zum nächsten Block gewechselt. Wenn der Algorithmus den Block findet, der das Element enthält, verwendet er den linearen Suchalgorithmus, um den genauen Index zu finden. Dieser Algorithmus ist schneller als die lineare Suche, aber langsamer als die binäre Suche.

Sprung-Such-Algorithmus

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

Beispiel für Sprungsuche

Angenommen, wir haben das Array: (1, 2, 3, 4, 5, 6, 7, 8, 9), und wir wollen X - 7 finden.

Da es 9 Elemente gibt, haben wir n als 9.

Implementierung des Sprungsuchalgorithmus

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

int jumpSearch(int arr[], int x, int n) {
  int m = sqrt(n);
  int i = 0;
  while (arr[min(m, n) - 1] < x) {
    i = m;
    m += sqrt(n);
    if (i >= n) return -1;
  }
  while (arr[i] < x) {
    i++;
    if (i == min(m, n)) return -1;
  }
  if (arr[i] == x) return i;

  return -1;
}

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

Komplexität des Sprungsuchalgorithmus

Zeitkomplexität

• Durchschnittlicher Fall

Der Sprungsortieralgorithmus läuft n/m mal, wobei n die Anzahl der Elemente und m die Blockgröße ist. Die lineare Suche erfordert m-1 Vergleiche, so dass der Gesamtzeitausdruck n/m + m-1 ist. Der optimalste Wert von m, der den Zeitausdruck minimiert, ist √n, wodurch die Zeitkomplexität n/√n + √n, d. h. √n beträgt. Die Zeitkomplexität des Sprung-Such-Algorithmus ist O(√n).

• Bester Fall

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

• Schlechtester Fall

Der ungünstigste Fall tritt ein, wenn wir n/m Sprünge machen und der letzte überprüfte Wert größer ist als das gesuchte Element und m-1 Vergleiche für die lineare Suche durchgeführt werden. Die Zeitkomplexität im schlimmsten Fall ist O(√n).

Raumkomplexität

Die Raumkomplexität dieses Algorithmus ist O(1), da er außer temporären Variablen keine weitere Datenstruktur benötigt.