Algorithmus – Suche überspringen

Angenommen, wir haben ein Array arr[] der Größe n und einen Block (zu springen) der Größe m. Dann durchsuchen wir die Indizes arr[0], arr[m], arr[2m]... ..arr[km] und so weiter. Sobald wir das Intervall gefunden haben (arr [km]

Wir betrachten das folgende Array: (0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610). Die Länge des Arrays beträgt 16. Bei einer Sprungsuche werden in den folgenden Schritten 55 gefunden, vorausgesetzt, die zu überspringende Blockgröße beträgt 4,

Schritt 1: Springe von Index 0 zu Index 4;
Schritt 2: Springen Sie von Index 4 zu Index 8;
Schritt 3: Springen Sie von Index 8 zu Index 16;
Schritt 4: Da das Element bei Index 16 größer als 55 ist, gehen wir einen Schritt zurück zu Index 9.
Schritt 5: Führen Sie eine lineare Suche ab Index 9 durch, um Element 55 zu erhalten.
Was ist die optimale Stückgröße zum Überspringen?
Im schlimmsten Fall müssen wir n/m Sprünge und m-1 Vergleiche mit einer linearen Suche durchführen, wenn der zuletzt überprüfte Wert größer als das gesuchte Element ist. Daher beträgt die Gesamtzahl der Vergleiche im ungünstigsten Fall ((n/m) + m-1). Wenn m =√n, ist der Wert der Funktion ((n/m) + m-1) der Minimalwert. Daher ist die beste Schrittgröße m = √n.

// C++ program to implement Jump Search

#include <bits>
using namespace std;

int jumpSearch(int arr[], int x, int n)
{
// Finding block size to be jumped
int step = sqrt(n);

// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[min(step, n)-1] = n)
return -1;
}

// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] 
<p>Ausgabe: </p>
<p>Nummer 55 ist bei Index 10</p>
<p>Zeitkomplexität: O(√n)<br>
Hilfsraum: O(1)</p>
<p><strong>Achtung:</strong></p>
<p>Diese Suche funktioniert nur bei sortierten Arrays. <br>
Die optimale Größe der zu überspringenden Blöcke ist O(√n). Dies macht die Sprungsuche O(√n) zeitlich komplex. <br>
Die zeitliche Komplexität der Sprungsuche liegt zwischen der linearen Suche ((O(n))) und der binären Suche (O(Log n) <br>).
Die binäre Suche ist besser als die Sprungsuche, aber die Sprungsuche hat den Vorteil, dass wir sie nur einmal durchlaufen (die binäre Suche erfordert möglicherweise höchstens 0 (Log n) Sprünge, wenn man bedenkt, dass das gesuchte Element das kleinste Element oder kleiner als das kleinste ist). Daher verwenden wir in Systemen, in denen das Zurückspringen teuer ist, die Sprungsuche. </p></bits>

Das obige ist der detaillierte Inhalt vonAlgorithmus – Suche überspringen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!